二叉搜索树

什么是二叉搜索树

二叉搜索树(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

所有的旋转调整都是把中间节点提上去