目录

二叉排序树的定义

二叉排序树的查找

二叉排序树的插入

二叉排序树的构造

二叉排序树的删除

查找效率分析

回顾

---

二叉排序树的定义

二叉排序树的查找

查找成功的情况

查找失败的情况

 

二叉排序树的插入

 

注意

（1）二叉排序树不允许出现重复的值，不能插入相同的结点，所以插入的元素如果是和之前的关键字相同，则插入失败。

（2）递归实现的最坏空间复杂度是O(h)

（3）新插入的结点一定是叶子结点

二叉排序树的构造

 

 二叉排序树的删除

（1）

 

（2）

 

 比如删除13结点和60结点后的效果

 

（3）

 

方法1：

找右子树的直接后继（通过中序排列）

 要删除50，用50的右子树，将右子树中序排列（60.61.63.65.66.70）最先访问的结点60，替代要删除的结点50的位置，

删除结果为

方法2：

找左子树（的直接前驱）中最大的值去替代要删除的结点，要删除的结点50的左子树最大的值30，所以用30代替50

 

删除后的结果如下：

查找效率分析

对比1次就是一层，2次就是第二层,依次类推......

比如：对于70的查找长度就是3次（三层）

对比次数肯定不会超过树的高度，

若树高h，找到最下层的一个结点需要对比h次
 

 

 查找最好情况就是像平衡二叉树那样

（平衡二叉树：树上任一个结点左子树和右子树的深度之差不超过1）

回顾