10-平衡二叉搜索树

首先，我们对前面介绍的二叉树进行复杂度的分析，假设我们现在按照7,4,9,2,5,8,11的顺序添加节点，那我们的添加顺序应该是这样的

如果我们要对二叉搜索树进行添加删除查找操作，我们是和每一层的元素进行比较，通过比较结果，来确定接下来是和左子树比较还是右子树比较，因此在进行添加删除查找操作时，比较的次数与树的高度有关。因此：二叉搜索树的添加删除查找操作，复杂度为O(h)，再由于如果该二叉树是一棵完全二叉树或者满二叉树的话，树的高度为logn，则复杂度为O(logn)

如果在前面添加节点时，是通过从小到大的顺序进行添加的话(即添加顺序为2,4,5,7,8,9,11)，则二叉树的结果为

在这种情况下，树的高度就与元素的个数相等了，这是的复杂度为O(h)，即为O(n)，在这种情况下，二叉搜索树退化成链表，并且在n比较大时，第一种添加方式和第二种添加方式的性能差距很大，如当n = 1000000时，二叉搜索树的最低高度为20

二叉搜索树退化成链表的另外一种情况

删除节点时也可能会导致二叉搜索树退化成链表，如下面二叉树

删除掉11后

删掉8以后

删掉9以后

最后删掉2以后

此时，二叉搜索树就退化成了链表

因此在添加删除节点时，都可能会导致二叉搜索树退化成链表

因此有没有办法防止二叉搜索树退化成链表？让添加，删除，搜索的复杂度维持在O(logn)

• 平衡(Balance)

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

例如下有节点相同的二叉树，可组成不同形状的二叉树

或者组成这样的二叉树

或者组成这样的二叉树

或者组成这样的二叉树

很明显，最后一个二叉树的左右子树是最接近的，通过以上几个不同的二叉树，可以看到，结果是越来越平衡

• 理想平衡

最理想的平衡，就是想完全二叉树，满二叉树一样，高度是最小的

如下列的两个二叉树

如何改进二叉搜索树

首先，节点的添加，删除顺序是无法限制的，可以认为是随机的，所以改进的方案是

• 在节点的添加，删除操作之后，想办法让二叉搜索树恢复平衡，即减小树的高度

例如有下列的二叉搜索树

我们往二叉树中添加一个新的节点后，变为

通过这一次添加以后，右子树的高度变为了4，左子树的高度为2

我们可以进行修改节点父子关系的方式，来减小树的高度

通过调整以后，树的高度减小了1，并且左右子树的高度更加接近，并且调整以后，二叉搜索树的性质依然不变

如果接着继续调整节点的位置，完全可以达到理想平衡，但是付出的代价可能会比较大，比如调整的次数会比较多，反而增加了时间复杂度，因此总结来说，比较合理的改进方案是:用尽量少的调整次数达到适度平衡即可。

一棵达到湿度平衡的二叉搜索树，可以成为平衡二叉搜索树

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

英文简称：BBST

经典常见的平衡二叉搜索树有

• AVL树
  • 在Windows NT内核中广泛使用
• 红黑树
  • C++ STL 中经常用到，如map,set
  • Java的TreeMap，TreeSet，HashMap，HashSet也有使用
  • Linux的进程调度
  • Ngix的timer管理

一般也称为:自平衡的二叉搜索树(Self-balancing Binary Search Tree)

GitHub地址
本节完！