文档介绍：第八章字典的树型实现
2016 Fall《数据结构》
二叉排序树
平衡二叉排序树(AVL树)
B-树
主要内容(掌握概念即可!)
*
*
二叉排序树
2017/12/9
第七章图
3
中序遍历序列是有序序列!
二叉排序树
或者为空树,或者是满足下列性质的二叉树:
若左子树不空,则左子树上的所有结点的值都小于根结点的值;
若右子树不空,则右子树上的所有结点的值都大于根结点的值
左右子树也分别为二叉排序树。
二叉排序树的定义(递归)
2017/12/9
第七章图
5
v
L
R
若根结点为空,则检索失败;
否则关键码与根关键码比较:
= :检索成功
< :转到左子树继续
> :转到右子树继续
二叉排序树的检索
2017/12/9
第七章图
6
二叉排序树的插入——为叶子
希望树形不要太“偏沉”,尽可能“平衡”,使得树的深度小,从而ASL小!
case 1:若要删除的结点是叶子,则直接删!
二叉排序树的删除
p
f
f
case 2:若要删除的结点只有一棵子树,则跨越删除!
二叉排序树的删除
p
f
L
R
q
f
L
R
q