基于树表的查找
二叉排序树
相关概念
存储结构
查找
具体实现
算法分析
插入
创建
删除
无孩子
有一个孩子
有左右孩子
示例
平衡二叉树
概念
示例
插入调整
类型
由插入结点在失衡结点的位置来定:插入结点C为失衡结点A的左子树的左孩子,因此为LL型。
原则
即选择中间结点作为新的树根,比其小的结点居左,比其大的结点居右,从而降低树高。
LL型
由调整原则可得:
取大小中间结点B作为根结点,插入结点比B小,A比根大,则分别作为其左右结点;
又因为B的右孩子比插入结点大,比A结点小,则作为A的左孩子
RR型
LR型
首先,找最小失衡子树;再用调整性原则进行调整。
最小失衡树由A B C三个结点组成。
其大小顺序为B<C<A,取中间结点C作为树根,则B A分别作为其左右孩子。
若C有左孩子,必定大于B,调整为B的右孩子;
若C有右孩子,必定小于A,调整为A的左孩子。
RL型
同理,首先,找最小失衡子树;再用调整性原则进行调整。
最小失衡树由A B C三个结点组成。
其大小顺序为A<C<B,取中间结点C作为树根,则A B分别作为其左右孩子。
若C有左孩子,必定大于A,调整为A的右孩子;
若C有右孩子,必定小于B,调整为B的左孩子。
示例
小结
调整过程就无需在意是左旋还是右旋,只需两个步骤:找最小失衡子树,结合调整原则。
删除调整
找最小失衡子树,按调整原则进行调整即可。
例1
无需调整,直接删除
例2
删除叶结点,还需向下调整
利用调整原则进行调整:
取中间结点80,比其小75作为其左孩子,比其大90作为其右孩子;
80有左孩子必定比75大,77作为75右孩子;
例3
删除结点有左右子树,
第一种:用前驱结点顶替(复制到)要删除的结点
利用调整性原则进行调整
第二种:用后继结点顶替(复制到)要删除的结点
利用失衡原则进行调整:
看成RR型,调整90为根结点
看成RL型,调整85作为根结点