算法 

解析红黑树

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 
Linux进程调度

评论

相关推荐

相关文章

Your browser is out-of-date!

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

×

分类
技术
展示
算法
存储
网络
数据
产品
读书
标签
Node.js
数学
一致性算法
MySQL
nginx
redis
Linux
微服务
大数据
语言
python
tcp/ip
spring