红黑树专题---学习学习

标签：Node 学习 node parent current --- 红黑树 节点 left

红黑树--------一

红黑树是一种平衡二叉树的优化树，所以红黑树的性质在平衡二叉树之上存在特有的性质

1、树的节点是红色或者黑色

2、树的根节点是黑色的

3、每个叶子节点，即空节点是黑色节点

4、如果一个节点是红色的，那么他的两个子节点都是黑色节点

5、对于每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点

 

//节点信息
template<class T>
class node
{
    node(T data_in);
    ~node(void);
    node* right;
    node* left;
    node* parent;
    T data;
    int color;//1是红色，2是黑色
}
//获取祖父节点
node grandparent(node n)
{
   return n->parent->parent;        
}
//获取叔叔节点
node uncle(node n)
{
   if(n->parent == grandparent(n)->left)
   return grandparent(n)->right;
   else
   return grandparent(n)->left;
}

从5的这个性质上，从根节点到叶子节点的最长路径不会超过最短路径的两倍，如下图所示：每个路径最多有N个黑色节点，假使全部是黑色节点，而红色节点不能连续，

所以最长路径就是黑红节点相间的路径，就是2N，只要存在连续的黑色节点，其长度肯定小于2N。

插入涉及的case1：插入的根节点为NULL，这时候插入节点直接设置为黑色即可，即作为Root节点

void case1(node n)
{
    if(n->parent == NULL)
    n->color = 0;
    else
    case2(n);
}

插入case2，新节点的父节点是黑色节点，直接插入即可，不需要修改原始树：

void case2(node n)
{
    if(n->parent->color == 0)
    return;
    else
    case3(n);
}

插入case3，新插入的父亲节点是红色，叔叔节点也是红色，按照如下处理之后，设置当前节点为祖父节点，然后执行再次插入操作即可

void case3(node n)
{
    if(uncle(n) != NULL && uncle(n)->color == RED)
    {
      n->parent->color =0;
      uncle(n)->color = 0;
     grandparent(n)->color = 1;
     case1(grandparent(n));
    }
    else
    case4(n);
}    

插入情况case4：父亲节点是红色，叔叔节点是黑色或者空节点，插入节点是父亲节点的右孩子，而父亲节点是祖父节点的左孩子，或者是父亲节点的左孩子，父亲节点是祖父节点的右孩子,实质上旋转之后就会走case5的情况处理

void case4(node n)
{
    if(n == n->parent->right && n->parent == grandparent(n)->left)
    {
        rotate_left(n->parent);
       n = n->left;
    }else if(n == n->parent->left && n->parent == grandparent(n)->right)
    {
       rotate_right(n->parent);
       n = n->parent;
    }
    case5(n);
}

插入case5：父亲节点是红色，而叔叔节点是黑色或者空节点，插入节点是父亲节点的左孩子，而父亲节点是祖父节点的左孩子

void case5(node n) {
     n->parent->color = BLACK;
     grandparent(n)->color = RED;
     if (n == n->parent->left && n->parent == grandparent(n)->left) {
         rotate_right(grandparent(n));
     } else {
         /* 反情况，N 是其父节点的右孩子，而父节点P又是其父G的右孩子 */
         rotate_left(grandparent(n));
     }
 }

 左旋右旋出现的原因在于，做了插入动作之后，由于出现了连续红色节点的不符合红黑树性质的节点，或者路径长度异常色问题，所以就出现左旋、右旋操作

左旋操作：父亲节点左旋,原则是父亲节点缺少的孩子由子节点多余的孩子补充，列举了右孩子情况，左孩子类似，可自行绘图学习

 

void rorate_left(node<T>* current_Node)
{
    node<T>* Right_child = current_Node->right;    
    node<T>* father_Node = current_Node->parent;
    current_Node->right = Right_child->left;
    Right_child->parent = father_Node;
    if (father_Node == NULL)
    {
        Root_Node = Right_child;
    }
    else if(current_Node == father_Node->left)
    {
        father_Node->left = Right_child;
    }
    else
    {
        father_Node->right = Right_child;
    }    

    Right_child->left = current_Node;
    current_Node->parent = Right_child;

}

右旋操作：父亲节点右旋，原则同上面一样

 

void rorate_right(node<T>* current_Node)
{
    node<T>* left_Node = current_Node->left;
    node<T>* father_Node = current_Node->parent;
    current_Node->left = left_Node->right;
    left_Node->right = current_Node;
    if (father_Node == NULL)
    {
        Root_Node = left_Node;
    }
    else if (current_Node = father_Node->left)
    {
        father_Node->left = left_Node;
    }
    else
    {
        father_Node->right = left_Node;
    }
    current_Node->parent = left_Node;
    left_Node->parent = father_Node;
}

 删除待续。。。。

标签：Node,学习,node,parent,current,---,红黑树,节点,left
From： https://www.cnblogs.com/sukkimy/p/17120302.html