===============
== 大程熙 ==
===============
一个小学生

数据结构之二叉排序树学习

二叉排序树重新学习。

二叉排序树的每个节点,其左子树上所有结点元素都小于该元素,其右子树上所有结点元素都大于该元素。

二叉排序树的查找操作

给定一个元素,查找该元素在二叉排序树中是否存在,其算法描述如下:

  1. 从根节点开始查找,设p指向根节点,如果要查找元素和p相等,则查找成功;
  2. 如果要查找元素比p小,则在p的左子树中继续查找。
  3. 如果要查找元素比p大,则在p的右子树中继续查找。
  4. 重复执行2、3直到查找成功或p为空。

二叉排序树的查找不需要遍历整棵树,查找非常快速。

二叉排序树的插入操作

将一个元素插入到二叉排序树中,需要先根据查找算法确定元素在二叉排序树中的位置,如果能查找到相等元素,说明已经插入过了不需要再次插入;如果查找不到,就在这条路径上的最后插入结点,作为叶子结点。

二叉排序树的删除操作

二叉排序树的删除操作首先需要查找该节点,如果存在,则分为三种情况:

  1. 要删除的结点是叶子结点
  2. 要删除的结点只有一个子树(左子树或者右子树)
  3. 要删除的结点有左右两个子树

第一种情况,要删除的结点是叶子结点,直接将要删除结点的父结点的left/right指针设置为null即可。

第二种情况,要删除的结点只有一个子树,直接将要删除结点的父结点的left/right指针指向删除结点的子树即可。

第三种情况,要删除结点有左右两个子树,有两种方式可选:第一种方式使用要删除的结点的左子树中的最大值来替换要删除的节点;第二种方式使用要删除结点的右子树中的最小值来替换要删除的结点。这两种是方式分别需要遍历要删除结点的左右子树,找到最大和最小值后,替换删除结点即可。

二叉排序树分析

时间复杂度

  • 最坏情况下,二叉排序树可能退化成链表,时间复杂度为O(n)
  • 正常情况下时间复杂度为$O(nlog_2n)$

缺点

二叉排序树在极端情况下可能退化成一个链表,时间复杂度变为O(n)。

可以使用平衡二叉树来解决二叉排序树的问题。

参考内容

  • 《数据结构(Java版)》