当前课程知识点：数据结构 > 第7章 查找 > 7.3 二叉排序树 > 讲解（下）
现在，我们来看第二个操作，插入
我们将关键字k，插入到二叉排序树当中
保证插入后的树，也是二叉排序树
要满足二叉排序树的性质
如果给定的关键字k，已经存在
这时候，我们放弃插入
因为我们前面说了，在二叉排序树当中
不允许出现重复的结点
每个结点的关键字，都得不一样
如果不存在
这时候，我们就可以插入了
刚才我们也分析过，插入位置
就是查找过程当中，最后一次被比较的那个结点
我们就将k，插入到那个结点的左孩子
或者右孩子上
也就是，刚才查找算法结束的时候
p所指向的那个结点
比如，刚才我们找85，不存在
这时候
p是指向88的
85就应该插入到88的左孩子上面
容易看出，新插入的结点，一定是作为叶结点的
现在，我们给出几个关键字
然后，我们依次把这些关键字，插入到一个初始为空的二叉排序树当中
第1个结点，没什么好说的
就是6
第2个结点
要插入7
我们是先找7，7跟6比较，大于6
然后，再在它的右子树上找
但是，6的右子树为空
这时候
p就指向6
我们就应该把7插到6的右子树上
第3个关键字2，依然是先找2，2如果存在
是在6的左子树上
(6的左子树)为空，不存在，这时候，就插到6的左子树上
第4个结点，也是类似的，插入5，我们先找5
沿着6的左孩子找，5大于2
沿着右孩子找，不存在
那么，插入到右孩子的位置
剩下的几个结点，都是类似的
我们就不详细说了
现在，我们来看二叉排序树的第三个操作
删除
将关键字k，从二叉排序树当中删除
并且保证，删除后的树
也是二叉排序树
如果要删除的k不存在
这时候，我们就放弃删除
如果存在，我们分为三种情况
第一种情况
如果要删除的k是叶结点
这时候，非常简单
直接删掉就行了
因为删除叶结点，不会影响二叉排序树的性质
比如，删除这里的3、4、1等等
这些结点，你直接删就可以了
并不会影响剩下的那些结点
第二种情况，若k只有左子树，让k的父结点指向k的左孩子
比如，我们现在删除4这个结点
k是指向4的
这时候
4只有左孩子
那我们只需要让4的父结点，指向4的左孩子，就行了
比如，我们把5的左孩子指针，绕过4，直接指向3
那如果我们删除的是5呢
这个5，它也只有左子树
这时候，也是一样的
我们让5的父结点2，指向5的左孩子，就可以了
也就是说
让2的右孩子指针，直接指向5的左孩子4
这样，也就相当于把5删除了
这里，有一个结点
我们如何找到呢
就是被删除结点
它的父结点是谁呢
大家还记得
我们刚才讲的查找算法当中的第三个参数f吗
这个f，始终指向我们找到的那个结点
也就是当前树的根T
它的父结点
这就是我们在查找算法当中，设置f那个参数的意义
主要是为了这里做删除的时候，找到k的父结点
这个就是我们前面查找算法结束时的f
我们再来看，与之对称的一种情况，k只有右子树
我们只需要让k的父结点，指向k的右孩子，就可以了
这个跟第二种情况，是对称的
我们就不再具体说了
现在，我们看最后一种，也就是最复杂的情况
k同时具有左右子树
这时候，我们应该怎么办呢
现在，我们单独把这种情况，拿出来讨论
比如，我们现在要删除的k，在这里
为了一般性
我把这棵树当中，比较重要的几个位置的结点，把它们画出来
事实上
在同时具有左右子树的时候
我们有好几种方式
我们先来看第一种方式
现在我们来看一下，左边的这棵树
S这个结点，它和k结点有什么关系呢
我们会发现
S这个结点，是k的左子树上最右的那个结点
大家听到这句话
马上就想到，二叉树的中序遍历
事实上
我们对一棵二叉排序树进行中序遍历，得到的序列
它是严格递增的
因为中序遍历，先左，再根，再右，根据BST树的性质
左子树是小于根
根是小于右子树的
你对二叉树进行中序遍历
这时候，得到的序列，一定是一个递增序列
也就是说，S它是小于k
这个k，是小于k的右子树KR，KR是小于P的
S和k具有什么关系呢
我们会发现，S是k的左子树上，最右的那个结点
也就是说，S是这棵二叉树中序遍历(所得序列中)k的前驱，中序遍历，k它前面的那个结点，就是S
现在，我们要删除k
k是同时具有左右子树的
而且，S小于k
并且小于KR
那我们可以直接将k删除
那可以删除
也就是，让k的父结点，指向k的左孩子
那k原来的右子树怎么办呢
既然KR是大于k的
它一定大于S
同时
KR也是小于P的
那我们就可以把KR，挪到S的右子树上，就可以了
也就是右边这个图
大家看到，右边这个图
我们直接把k删除
也就是，让k的父结点P
它的左孩子指针，直接指向k的左子树C
然后
将原来k的右子树KR，作为中序遍历当中，k的前驱S的右孩子
这样，是不会改变删除了k之后，剩下的几个结点之间的大小关系的
所以这种方式，我们要做的就是，让k的父结点P，指向k的左孩子
然后，将k的右子树KR，作为k的中序前驱
也就是S，它的右子树
有些同学可能会问
如果S它本来就有右子树呢
它本来就有右子树
这时候，如何将KR作为S的右子树呢
如果S有右子树
那k的中序前驱，就不是这里的S了
而是它右子树上，最右的那个结点
所以，没有必要担心这种问题
现在，我们来看第二种方式
这种方式
是用k的中序前驱替换k，并不是删除k
而是用一个结点来替换k，k的右子树KR
保持不动
现在，谁来替换k呢
一样的
我们用k的中序遍历它的前驱S，来替换
也就是，k的左子树上，最右的那个结点
用S来替换k
那S这个结点，它得删掉
第二步，就是删除S，删除S，不就回到了我们之前的第二种情况吗
S只有左子树
有的同学可能会问
如果S它又有左子树
又有右子树
这时候怎么办呢
你删除S，不是又递归回到了我现在要讲的
同时具有左右子树的这种情况吗
跟刚才类似
如果S它同时具有左右子树
特别是它有右子树
那k的中序前驱，就不是S了
而是它右子树上，最右的那个结点了
所以，这种情况，我们也没必要担心，我们只画出了
S具有左子树
再来回顾一下，第二种方式
直接用k的中序前驱，也就是k的左子树上，最右的那个结点
替换k
k原来的右子树KR不变
依然是作为S的右子树
原来的S，把它删掉
这样，就回到了我们刚才讲的第二种情况
S只有左子树
那我们就用S的父结点，指向S的左孩子，就可以了
这是二叉排序树的删除
现在，我们来分析二叉排序树的查找性能
我们依然是用前面介绍的平均查找长度这个指标来衡量
三种情况
第一种，最坏的情况，最坏的情况下
二叉排序树当中，每一层只有一个结点
那我们找第1层的结点
经历1次比较
第2层，经历2次比较
第i层，经历i次比较
最后的平均查找长度，在等概率的情况下
就是Σi做一个算术平均
事实上
在这种情况下
查找，就变成了一个我们前面介绍的顺序查找
因为
在这种情况下
二叉排序树，退化成了一个线性表
每一层只有一个结点
我们再来看第二种情况
最好的情况
最好的情况，树是完全二叉树
或者说，是我们前面介绍的折半查找，对应的判定树
我们之前已经介绍过，折半查找
它的平均查找长度，是这个
一般的情况下
它的平均查找长度，是log2(n)
我们这里，就不给出这个log2(n)
它的推导过程了
大家观察一下
在最好情况和一般情况下，这二者的平均查找长度
当n比较大的时候
实际上，它们是非常接近的
这时候的树的情形
就是介于这两种形态之间
介于这二者之间
既不像前面最坏的情况
每一层只有一个结点
也不像最好的情况
完全二叉树
我们看最坏的情况，平均查找长度
是线性级的
最好的情况，是对数级的，当n比较大的时候
这二者相差还是非常多的
那我们应该让二叉排序树，尽可能地向完全二叉树的形态靠拢
而不要出现，每一层只有一个结点
这种情况
也就是说，我们应该让二叉排序树，每一个结点的
左右子树的高度差不多
不要相差太多
那也就是，我们即将介绍的
平衡二叉树
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
