什么是二叉搜索树
二叉搜索树(BST，Binary Search Tree)， 也称二叉排序树或二叉查找树
二叉搜索树:一棵二叉树，可以为空;如果不为空，满足以下性质:
- 非空左子树的所有键值小于其根结点的键值。
- 非空右子树的所有键值大于其根结点的键值。
-
左、右子树都是二叉搜索树。
serachTree.png
二叉搜索树的查找操作:Find
SerachTreeFind.png
查找最大和最小元素
最大元素一定是在树的最右分枝的端结点上
最小元素一定是在树的最左分枝的端结点上
二叉搜索树的插入
关键是要找到元素应该插入的位置， 可以采用与Find类似的方法
二叉搜索树的删除
- 要删除的是叶结点:直接删除，并再修改其父结点指针---置为NULL
- 要删除的结点只有一个孩子结点: 将其父结点的指针指向要删除结点的孩子结点
-
要删除的结点有左、右两棵子树 用另一结点替代被删除结点:右子树的最小元素 或者 左子树的最大元素
deleteSerachTree.png
平衡二叉树
什么是平衡二叉树
搜索树结点不同插入次序，将导致不同的深度和平均查找长度ASL
为了缩短平均查找长度，引入了平衡二叉树的概念
“平衡因子(Balance Factor，简称BF): BF(T) = hL-hR， 其中hL和hR分别为T的左、右子树的高度。
平衡二叉树(Balanced Binary Tree)(AVL树) 空树，或者
任一结点左、右子树高度差的绝对值不超过1，即|BF(T) |≤ 1
banlanceTree.png
banlanceTree1.png
平衡二叉树的调整
- 不平衡的“发现者”是Mar，“麻烦结点”Nov 在发现者右子树的右边， 因而叫 RR 插入，需要RR 旋转(右单旋)
RR.png
- 发现者”是Mar，“麻烦结点”Apr 在发现者左子树的左边， 因而叫 LL 插入，需要LL 旋转(左单旋)
LL.png
-
发现者”是May，“麻烦结点”Jan在左子树的右边， 因而叫 LR 插入，需要LR 旋转
LR.png
-
发现者”是May，“麻烦结点”Jan在右子树的左边， 因而叫 LR 插入，需要LR 旋转
RL.png
所有的旋转调整都是把中间节点提上去
