从2-3-4树到红黑树

Red–black tree是一种自平衡二叉查找树，是计算机科学常用到的一种数据结构，典型的用途是实现Associative Array，就是定义一堆key去关联value（如果说关联数组又叫Map或者Dictionary是不是顿时感觉亲切了许多呢）

1.概念准备

1.1.BST

二叉查找树（Binary Search Tree）是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。

1.2.AVL Tree

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)所以Red–black tree也有同样的性能。

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。节点的平衡因子是它的左子树的高度减去它的右子树的高度，带有平衡因子1、0或-1的节点被认为是平衡的。带有平衡因子-2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

1.3.2-3-4 Tree

二叉查找树。每个节点只可以有一个key，而2-3-4树就是将节点的key的数量增加，可以有多个key，并且2-3-4树可以保持完美平衡（Perfect balance）。

234是指子节点数量，3节点有两个key把所有的child分成了三拨，4节点有3个key把子节点分成4拨。

2.从2-3-4树到红黑树

红黑树是2-3-4树的一种等效树。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。

红黑树在原有的二叉查找树基础上增加了如下几个要求

• 1.Every node is either red or black.
• 2.The root is black.
• 3.Every leaf (NIL) is black.
• 4.If a node is red, then both its children are black.
• 5.For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

简单说红黑树满足三条

1. 首尾节点全黑：根节点和每个叶子节点（NIL）是黑色。[1.2.3]
2. 红节点子全黑：如果一个节点是红色的，则它的子节点必须是黑色的。[4]
3. 黑节点数相同：从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。[5]

   
            B80
           /    \
        R40     R120
        /  \       \
    B20     B60     B140 
    / \     / \     / \
     R10 Nil R50 Nil R10 R30
     / \      /\     / \ / \
   Nil Nil  Nil Nil Nil Nil Nil
   

   2.1.红黑树的旋转操作

   对4进行左旋，意味着将4变成一个原位置节点的左节点。

        8                               8     
       / \                             / \
      4   12    =leftrotate(4)=>      6   12
    /  \                             / \
   2    6                           4   7
       / \                         / \
      5   7                       2   5
   

   对比234树的操作把节点4升级成3NodeTree，上图旋转前的情况是选择把4提升为父节点，左旋转是换成了把6提成成父节点,这样理解的话右旋就是相反的操作。节点4左旋就是通过旋转操作把4变成6的左节点，。

            8
           / \
         4|6  12
        / | \
       2  5  7