数据结构与算法：二叉树->平衡二叉树->红黑树

1.什么是二叉查找树？

一棵空树，或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 左、右子树也分别为二叉排序树；
• 没有键值相等的节点

二叉树.gif

2.什么是二叉查找树的“瘸腿”问题？

“瘸腿”：如图所示，左腿或者右腿特别长，也就是说这些数据构成的二叉树不平衡。

“瘸腿”二叉树.gif

3.如何解决二叉树的“瘸腿”问题？

为了使二叉树变得平衡，我们需要保证每个左边的树的层次和右边的树的层次相差不超过1。所以问题就变成了怎么保证每个左边的树的层次和右边的树的层次相差不超过1？

• 3.1 当节点右边层数比右左边层数大于1的时候，对树进行左旋

  
  左旋.gif
• 3.2 当节点左边边层数比右边层数大于1的时候，对树进行右旋
  右旋.gif
  综上，通过左旋和右旋保证所有节点的左右子树高度差不超过1，也就解决二叉树的"瘸腿"，进而实现二叉树的平衡，这就是平衡二叉树。但每次插入都要去判别是否需要旋转，而旋转的代价又比较大，这样，在插入多，查找少的情况下就会显得得不偿失。所以，接下来问题就是怎么解决平衡二叉树的效率问题？

4.如何解决平衡二叉树的效率问题？

平衡二叉树由于频繁左旋和右旋导致在频繁插入的情况下效率较低，所以取了折中的方案：减少选择旋转的次数。也就是由所有节点的左右子树高度差不超过1妥协为不超过短的那棵树高度一倍，举例：某个节点左子树的高度是2，那么该节点的右子树的高度不能超过4。具体的实现方式一种就是红黑树。

图示.gif