红黑树与二叉查找树(BST)与AVL树

1.二叉查找树（BST）Binary Search Tree

• 特点：
  1.左子树上所有结点的值均小于或等于它的根结点的值。

  2.右子树上所有结点的值均大于或等于它的根结点的值。

  3.左、右子树也分别为二叉排序树。

• 下图中这棵树，就是一颗典型的二叉查找树：
  

• 但是BST的弊端：

​ 假设初始的二叉查找树只有三个结点，根结点值为9，左孩子值为8，右孩子值为12：

接下来我们依次插入如下五个结点：7,6,5,4,3。依照二叉查找树的特性，结果会变成什么样呢？

好端端的二叉树变成了“瘸子”。如何解决二叉树多次插入新节点导致的不平衡呢？红黑树应运而生啦。

2. 红黑树（Red Black Tree)

• 是一种自平衡的二叉查找树，除了符合二叉查找树的基本特性外，它还具有下列规则：

  1.结点是红色或黑色。

  2.根结点是黑色。

  3.每个叶子结点都是黑色的空结点（NIL结点）。

  4.每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)

  5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

• 下图中这棵树，就是一颗典型的红黑树：
  

• 红黑树从根到叶子的最长路径不会超过最短路径的2倍。

• 当插入或者删除结点的时候，上述红黑树的规则有可能会被打破。这个时候就需要做出一些调整，从而继续维持其规则。

  调整的方法包括两种：变色和旋转，旋转分为左旋转和右旋转

• 变色：为了重新符合红黑树的规则，尝试把红色结点变为黑色，或者把黑色结点变为红色。

• 左旋转：

  逆时针旋转红黑树的两个结点，使得父结点被自己的右孩子取代，而自己成为自己的左孩子。
  
  图中，身为右孩子的Y取代了X的位置，而X变成了自己的左孩子。此为左旋转。

• 右旋转：

  顺时针旋转红黑树的两个结点，使得父结点被自己的左孩子取代，而自己成为自己的右孩子。
  
  图中，身为左孩子的Y取代了X的位置，而X变成了自己的右孩子。此为右旋转。

3. AVL树

• AVL树是严格平衡的二叉树，要求每个节点的左右子树高度差不超过1；而红黑树则要宽松些，要求任何一个路径的长度不超过其他路径长度的2倍。

• 正是因为这个差别，AVL树的查找效率更高，但平衡调整的成本也更高。在需要频繁查找时，选用AVL树更合适，在需要频繁插入删除时，选用红黑树更合适。

欢迎关注公众号，干货满满。