左倾红黑树（插入操作）详解

前置知识 ：红黑树。

左倾红黑树（LLRB）是红黑树的一种变体。相比于标准红黑树，它的实现要简单得多，同时依然能够保证所有查找、删除和插入操作都在 O(logn) 的时间内完成。

哪些节点是红色的，哪些是黑色的？

拥有两条入边的节点是红色的。

拥有单条入边的节点是黑色的。

LLRB 的特性

• 根节点始终是黑色的。
• 每个新插入的节点始终是红色的。
• 节点的每个 NULL 子节点都被视为黑色。

例如：树中只有 40 这一个节点的情况。

root
       |
       40 <-- 因为 40 是根节点，所以它
      /  \    也是黑色的。
    NULL  NULL <-- 黑色。

• 不应存在一个节点，它拥有右侧红色子节点且左侧为黑色子节点（或 NULL，因为所有 NULL 都是黑色）。如果存在这种情况，我们需要左旋该节点，并交换当前节点与其左子节点的颜色，以保持规则 2 的一致性，即新节点必须是红色的。

CASE 1.
   root                        root     
     |                          ||      
     40      LeftRotate(40)     50     
    /  \\        --->          /  \    
  NULL  50                   40   NULL    

                               root              
                                |               
         ColorSwap(50, 40)      50 
           --->               //  \              
                             40  NULL

• 不应存在一个节点，它拥有左侧红色子节点且左侧孙节点也是红色。如果存在这种情况，我们需要右旋该节点，并交换该节点与其右子节点的颜色，以遵循规则 2。

CASE 2.
   root                         root      
    |                            ||        
    40        RightRotate(40)    20        
   //  \         --->          //   \      
  20    50                    10    40           
 //                                   \      
10                                     50

                          root
                           |
    ColorSwap(20, 40)      20
      --->                // \\
                         10   40
                               \
                               50

• 不应存在一个节点，它同时拥有左侧红色子节点和右侧红色子节点。如果存在这种情况，我们需要反转所有节点的颜色，即当前节点、左子节点和右子节点。

CASE 3.
   root                           root      
    |       !color(20, 10, 30)     ||       
    20            --->             20                
  //  \\                          /  \  
 10    30                        10  30 

                                     root
        As the root is always black    |                     
                --->                  20   
                                     /  \
                                   10   30

为什么要遵循上述规则？因为通过遵循这些特性/规则，我们能够模拟所有标准红黑树的性质，而无需关心其复杂的实现过程。

示例：

将以下数据插入到左倾红黑树中
并显示树的中序遍历结果。
输入 : 10 20 30 40 50 25
输出 : 10 20 30 40 50 25
        root
         |
         40
       //  \
      20    50
     /  \
   10    30
        //
       25

方法：

在 LLRB 中的插入操作与在二叉搜索树中的插入完全相同。不同之处在于，在我们将节点插入树之后，我们需要回溯到根节点，并尝试对 LLRB 强制执行上述规则。

在进行上述旋转和颜色交换的过程中，我们的根节点可能会变成红色，这一点我们也必须注意。我们必须确保根节点始终保持黑色。

!LLRB insertion Example.

C++


“

// C++ program to implement insert operation

// in Red Black Tree.

#include

using namespace std;

typedef struct node

{

struct node left, right;

int data;

// red ==> true, black ==> false

bool color;

}node;

// Utility function to create a node.

node* createNode(int data, bool color)

{

node *myNode = new node();

myNode -> left = myNode -> right = NULL;

myNode -> data = data;

// New Node which is created is

// always red in color.

myNode -> color = true;

return myNode;

}

// Utility function to rotate node anticlockwise.

node rotateLeft(node myNode)

{

cout << "left rotation!!

";

node *child = myNode -> right;

node *childLeft = child -> left;

child -> left = myNode;

myNode -> right = childLeft;

return child;

}

// Utility function to rotate node clockwise.

node rotateRight(node myNode)

{

cout