解析红黑树

0. 前言

前边Nginx中定时器的实现,以及Linux中完全公平算法都用了红黑树,是时候对它进行整理了。

红黑树是一种二叉平衡树,下边先来看看二叉搜索树,毕竟红黑树的用法与二叉树的用法基本是类似的;然后来看看红黑树的原理,为了更好的理解红黑树,我们对照2-3-4树来看;最后来看看红黑树的实现。

1. 二叉搜索树

定义:对于任何结点x,其左子树的关键字最大不超过x,其右子树的关键字最小不低于x。

二叉搜索树

每个结点,除了key和卫星数据之外,每个结点还包括left、right和p(parent)指针。

以下代码都是伪码

查找

  • 遍历

    遍历根据输出关键字的位置位于左子树和右子树的位置,可以分成中序遍历(inorder)、前序遍历(preorder)、后序遍历(postorder)。

    void inorderTreeWalk(x){
        if(x != null){
            inorderTreeWalk(x.left);
            print(x.key);
            inorderTreeWalk(x.right);
        }
    }
    
  • 搜索

    二叉搜索树就是为了查找设计的,过程如下:

    TreeNode treeSearch(x, k){
        if(x==null || k==x.key){
            return x;
        }
        if(k < x.key)
            return treeSearch(x.left, k);
        else
            return treeSearch(x.right, k);
    }
    

    除了递归的方式,还可以写成循环的方式:

    TreeNode iterativeTreeSearch(x, k){
        while (x!=null && k!=x.key){
            if(k < x.key)
                x = x.left;
            else 
                x = x.right;
        }
        return x;
    }
    
  • 最大与最小节点

    最小值是最左侧的节点,最大值最右侧的节点。

    TreeNode treeMinimum(x){
        while(x.left != null){
            x = x.left;
        }
        return x;
    }
    
    TreeNode treeMaxium(x){
        while (x.right != null){
            x = x.right;
        }
        return x;
    }
    
  • 后继与前驱

    后继(Successor)指的是比该节点大的元素中最小的;前驱(Predecessor)是比该节点小的中最大的。

    二叉搜索树的前继与后驱

    如图:对于11而言,10是它的前继,12是它的后驱。但对于10而言,11是它的后驱;对于12而言,11是它的前继。

    前继:

    TreeNode treePredecessor(x){
        // 11 -> 10
        if(x.left != null)
            return treeMaxium(x.left);
        // 12 -> 11
        y = x.p;
        while(y!=null && x==y.left){
            x = y;
            y = y.p;
        }
        return y;
    }
    

    后驱:

    TreeNode treeSuccessor(x){
        // 11 -> 12
        if (x.right != null)
            return treeMinimum(x.right);
        // 10 -> 11
        y = x.p;
        while (y!=null && x==y.right){
            x = y;
            y = y.p;
        }
        return y;
    }
    

    以上几个操作二叉搜索树与红黑树是相同的,这几个算是树的使用;下边的插入与删除,则不同,算是树的生成与调整。

插入

插入的过程是根据要插入的key,找到合适的位置,并且修改其父节点指向的过程。

void treeInsert(T, z){
    y = null;
    x = T.root;
    while(x != null){
        y = x;
        if(z.key < x.key)
            x = x.left;
        else
            x = x.right;
    }
    z.p = y;
    // 更新父节点
    if (y == null)
        T.root = z;						// 空树
    else if (z.key < y.key)
        y.left = z;
    else
        y.right = z
}

删除

删除是插入的逆运算,但比插入会复杂一些,因为删除时不光要考虑其自身与父节点,还要考虑其子节点。它分成3种情况:

  • 如果z没有孩子节点,删除该节点,更新父节点
  • 如果z只有1个孩子,那么将该孩子提升到z的位置,并修改z的父节点的相关指针指向z
  • 如果z有2个孩子,那么可以先从找到z的后继(也可以是前驱)y,然后用y来替换z
// 用v替换u
void transplant(T, u, v){
    if (u.p == null)
        T.root = v;
    else if (u ==u.p.left)
        u.p.left = v;
    else 
        u.p.right = v;
   	if (v != null)
        v.p = u.p;
}

void treeDelete(T, z){
    if (z.left == null)
        transplant(T, z, z.right);
    else if(z.right == null)
        transplant(T, z, z.left);
    else {
        // 求后继y,用后继替换被删节点
        y = treeMinimum(z.right);
        if (y.p != z){
            // 优化,移除y,并更新右侧
            transplant(T, y, y.right);
            y.right = z.right;
            y.right.p = y;
        }
        // y 替换 z
        transplant(T, z, y);
        y.left = z.left;
        y.left.p = y;
    }
}

2. 红黑树原理

普通的二叉搜索树容易退化成链表,而红黑树是一种平衡的搜索树,它不会退化成链表。

红黑树在每个节点上增加一个存储位来表示节点的颜色,可以使RED或者BLACK。通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束,红黑树确保没有条路径比其他路径长出2倍,因而是近似于平衡的。

红黑树性质

  1. 节点是红色或者黑色
  2. 根节点是黑色
  3. 每个红节点必须有2个黑色的子节点
  4. 从任一节点到每个叶子节点的所有简单路径都包含 相同数目的黑色节点

红黑树降维

将红黑树所有的红节点与其父节点合并成一个节点

这个新形成的树称之为2-3-4树,因为它可能2个子节点、3个子节点或者4个子节点。

性质简化

这样红黑树的4条性质:

  1. 节点是红色或者黑色
  2. 根节点是黑色
  3. 每个红节点必须有2个黑色的子节点
  4. 从任一节点到每个叶子节点的所有简单路径都包含 相同数目的黑色节点

就简化成2-3-4树的2条性质:

  1. 节点只能是2节点、3节点、4节点之一,合并之后的元素最多有3个(4节点)
  2. 所有叶子节点的具有相同的深度,合并之后只剩黑节点,具有相同的深度。

相当于用空间属性替换了红黑的属性,降低了维度。

3. 红黑树操作

下边我们通过新变化的2-3-4树的操作反过来研究红黑树的操作,这里的操作指的是Insert与Delete2个操作。

插入

2-3-4树的插入的规则:

  • 插入:从最下层参入;
  • 升元:将插入结点由 2-结点升级成 3-结点,或由 3-结点升级成 4-结点;
  • 递归升高:向 4-结点插入元素,先将中间元素提到父结点升元,原结点变成两个 2-结点,再把元素插入 2-结点中,如果父结点也是 4-结点,则递归向上层升元,至到根结点后将树高加1;

对应到红黑树里,就是:

  • 新插入的结点颜色为红色,这样才可能不会对红黑树的高度产生影响。
  • 2-结点对应红黑树中的单个黑色结点,插入时直接成功(对应 2-结点升元)。
  • 3-结点对应红黑树中的黑+红子树,插入后将其修复成 红+黑+红 子树(对应 3-结点升元);
  • 4-结点对应红黑树中的红+黑+红子树,插入后将其修复成红色祖父+黑色父叔+红色孩子子树,然后再把祖父结点当成新插入的红色结点递归向上层修复,直至修复成功或遇到 root 结点;
红黑树的插入

这里将3->4 写了2个,虽然对于2-3-4树差别不大,但对于红黑树的实现还是有区别。11与12再加13时,只需要将13挂在12右子节点,然后左旋转12即可。对与11与13再加12时,需要先右旋一下12,然后再左旋一下12。

删除

对于二叉搜索树而言,删除是查询其后继,做了替换,在这里也是如此。

2-3-4树规则:

  • 替换:查找离其最近的叶子节点(后继或前驱)替代被删除元素,然后从后继(或前驱)节点开始从下往上开始调整;
  • 直接降元:4-结点变 3-结点,3-结点变 2-结点;
  • 借元:2-结点中只有一个元素,删掉会造成树的深度不一致,所以下边会通过借点的方式来补充:
    • 借兄弟结点中的元素来补充删除后的造成的空结点;
    • 当兄弟结点中也没有多个元素可以补充时,尝试将父结点降元(兄弟与父亲借元的顺序可以颠倒);
    • 当父节点失败时向上递归,至到子树降元成功或到 root 结点树高减1;

将这些规则对应到红黑树中即:

  • 替换:查找后继(或前驱)节点来替换被删节点(如果被删是叶子节点,则不需要),从替代的叶子结点向上递归调整
  • 直接降元:替代结点颜色为红色(对应 2-3-4树中 4-结点或 3-结点)时删除子结点直接成功;
  • 借元:替代结点为黑色(对应 2-3-4树中 2-结点)时,意味着替代结点所在的子树会降一层,需要依次检验以下三项,以恢复子树高度:
    • 兄弟结点的子结点中有红色结点(兄弟结点对应 3-结点或 4-结点)能够“借用”,旋转过来后修正颜色;
    • 父结点是红色结点(父结点对应 3-结点或 4-结点,可以降元)时,将父结点变黑色,自身和兄弟结点变红色后删除;
    • 父结点和兄弟结点都是黑色时,将子树降一层后把父结点当作替代结点递归向上处理。

调整的过程如下图所示:

红黑树删除

上图并没画出全部情况。最后递归借元,如下:

红黑树删除递归情况
  1. 先合并父亲与兄弟节点
  2. 然后相当于删除父亲节点,从叔叔、祖父节点来充当父亲,依此递归

借鉴:通过2-3-4树理解红黑树

4. 具体实现

具体的实现参考:红黑树,这里仅摘抄部分代码

插入

void insert(Node *p, int data){
        if(p->value >= data){
            if(p->leftTree != NIL)
                insert(p->leftTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->leftTree = tmp;
                insert_case (tmp);
            }
        } else {
            if(p->rightTree != NIL)
                insert(p->rightTree, data);
            else {
                Node *tmp = new Node();
                tmp->value = data;
                tmp->leftTree = tmp->rightTree = NIL;
                tmp->parent = p;
                p->rightTree = tmp;
                insert_case (tmp);
            }
        }
    }

    void insert_case(Node *p){
        if(p->parent == NULL){
            root = p;
            p->color = BLACK;
            return;
        }
        if(p->parent->color == RED){
            if(p->uncle()->color == RED) {
                p->parent->color = p->uncle()->color = BLACK;
                p->grandparent()->color = RED;
                insert_case(p->grandparent());
            } else {
                if(p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {
                    rotate_left(p);
                    p->color = BLACK;
                    p->parent->color = RED;
                    rotate_right(p);
                } else if(p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {
                    rotate_right(p);
                    p->color = BLACK;
                    p->parent->color = RED;
                    rotate_left(p);
                } else if(p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_right(p->parent);
                } else if(p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {
                    p->parent->color = BLACK;
                    p->grandparent()->color = RED;
                    rotate_left(p->parent);
                }
            }
        }
    }

删除

bool delete_child(Node *p, int data){
        if(p->value > data){
            if(p->leftTree == NIL){
                return false;
            }
            return delete_child(p->leftTree, data);
        } else if(p->value < data){
            if(p->rightTree == NIL){
                return false;
            }
            return delete_child(p->rightTree, data);
        } else if(p->value == data){
            if(p->rightTree == NIL){
                delete_one_child (p);
                return true;
            }
            Node *smallest = getSmallestChild(p->rightTree);
            swap(p->value, smallest->value);
            delete_one_child (smallest);

            return true;
        }else{
           return false;
         }
    }

    void delete_one_child(Node *p){
        Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
        if(p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL){
            p = NULL;
            root = p;
            return;
        }
        
        if(p->parent == NULL){
            delete  p;
            child->parent = NULL;
            root = child;
            root->color = BLACK;
            return;
        }
        
        if(p->parent->leftTree == p){
            p->parent->leftTree = child;
        } else {
            p->parent->rightTree = child;
        }
        child->parent = p->parent;

        if(p->color == BLACK){
            if(child->color == RED){
                child->color = BLACK;
            } else
                delete_case (child);
        }

        delete p;
    }

    void delete_case(Node *p){
        if(p->parent == NULL){
            p->color = BLACK;
            return;
        }
        if(p->sibling()->color == RED) {
            p->parent->color = RED;
            p->sibling()->color = BLACK;
            if(p == p->parent->leftTree)
                //rotate_left(p->sibling());
                rotate_left(p->parent);
            else
                //rotate_right(p->sibling());
                rotate_right(p->parent);
        }
        if(p->parent->color == BLACK && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            delete_case(p->parent);
        } else if(p->parent->color == RED && p->sibling()->color == BLACK
                && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
            p->sibling()->color = RED;
            p->parent->color = BLACK;
        } else {
            if(p->sibling()->color == BLACK) {
                if(p == p->parent->leftTree && p->sibling()->leftTree->color == RED
                        && p->sibling()->rightTree->color == BLACK) {
                    p->sibling()->color = RED;
                    p->sibling()->leftTree->color = BLACK;
                    rotate_right(p->sibling()->leftTree);
                } else if(p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
                        && p->sibling()->rightTree->color == RED) {
                    p->sibling()->color = RED;
                    p->sibling()->rightTree->color = BLACK;
                    rotate_left(p->sibling()->rightTree);
                }
            }
            p->sibling()->color = p->parent->color;
            p->parent->color = BLACK;
            if(p == p->parent->leftTree){
                p->sibling()->rightTree->color = BLACK;
                rotate_left(p->sibling());
            } else {
                p->sibling()->leftTree->color = BLACK;
                rotate_right(p->sibling());
            }
        }
    }
# Linux  nginx 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×