第7章. 平衡二叉搜索树

平衡二叉搜索树(Balanced Binary Search Tree)

1.1 二叉搜索树存在的问题

添加、删除节点时，都可能导致二叉搜索树退化成链表。为了防止二叉搜索树退化成链表，让添加、删除搜索的复杂度维持在O(logn)，提出平衡的概念。

1.2 平衡(Balance)

平衡：当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡(高度差低)

1.3 理想平衡

最理想的平衡，就是像完全二叉树、满二叉树那样，高度是最小的。

1.4 如何改进二叉搜索树？

首先，节点的添加、删除顺序是无法限制的，可以认为是随机的

所以，改进方案是：在节点的添加、删除操作之后，想办法让平衡搜索树恢复平衡(减小树的高度)

总之，一棵平衡二叉搜索树，完全可以达到理想平衡，但是付出的代价可能会变大。比如调整的次数比较多，反而增加了时间复杂度。

比较合适的改进方案是：用尽量少的调整次数达到适度平衡即可。

一棵达到适度平衡的二叉搜索树，可以称为：平衡二叉搜索树。

1.5 平衡二叉搜索树(Banlanced Binary Search Tree，BBST)

• 英文简称：BBST
• 常见的平衡二叉搜索树：
• AVL树
  • Windows NT内核中广泛使用
• 红黑树
  • C++ STL(比如map、set)
  • Java的TreeMap、TreeSet、HashMap、HashSet
  • Linux的进程调度
  • Ngix的timer管理
• 一般也称它们为：自平衡的二叉搜索树(Self-balancing Binary Search Tree)