算法笔记:红黑树

zhenghaoz 等级 590 0 0
标签: 红黑树C/C++

红黑树,一种平衡二叉树,最为著名的应用就是C++ STL中的map,是有序集合最为理想的存储方式之一。除了二叉树所具有的属性之后,红黑树中每个节点多了一个“颜色”属性,可以是红色或者是黑色。一棵红黑树应该满足一下的性质:

  1. 每个节点是红色或者黑色的;
  2. 根节点是黑色的;
  3. 每个叶节点nil是黑色的(使用哨兵节点在删除调整时可以方便不少);
  4. 如果一个节点是红色的,那么它的两个子节点是黑色的;
  5. 对于每一个节点,到后代所有叶节点所经过的黑色节点数目相同。

根据定义,可以写出红黑树节点的数据结构:

struct Node {
    enum Color { RED, BLACK };
    Color _color;
    Key _key;
    Value _value;
    Node *_parent, *_left, *_right;
    Node(): _color(BLACK) {}
    Node(const Key &key, const Value &value, Node *left, Node *right, Node *parent):
        _key(key), _value(value), _color(RED), _left(left), _right(right), _parent(parent) {}
};

本文省略了拷贝、析构、赋值等操作,完整源代码放在Gist上。

旋转

想要红黑树维持着平衡,就需要在插入元素和删除元素的过程中不断对结构进行调整。其中,最基础的操作就是左旋右旋

算法笔记:红黑树

以左旋为例,操作可以分为三步:

  1. 将Q的左子节点变成P的右子节点;
  2. 将P变成Q的左子节点;
  3. 将Q变成当前子树的根节点。
void leftRotate(Node *x)
{
    Node *y = x->_right;
    // remove y->left to x->right
    x->_right = y->_left;
    if (x->_right != nil)
        x->_right->_parent = x;
    // remove y up
    y->_parent = x->_parent;
    if (x->_parent == nil)
        root = y;
    else if (x->_parent->_left == x)
        x->_parent->_left = y;
    else
        x->_parent->_right = y;
    // remove x down
    x->_parent = y;
    y->_left = x;
}

插入

先污染,后治理。首选按照二叉树的插入方法先将节点插入二叉树,然后再对红黑树进行调整。

void insert(Node *nptr)
{
    Node *it = root, *p = root;
    // find insert position
    while (it != nil) {
        p = it;
        if (nptr->_key < it->_key)
            it = it->_left;
        else if (nptr->_key > it->_key)
            it = it->_right;
        else {
            // find target key-value
            it->_value = nptr->_value;
            return;
        }
    }
    // insert
    nptr->_parent = p;
    if (p == nil)
        root = nptr;
    else if (nptr->_key < p->_key)
        p->_left = nptr;
    else
        p->_right = nptr;
    // fixup
    insertFixup(nptr);
}

在完成插入之后,将面临六种情况,由于存在左右对称的情况,实际上只需要考虑三种情况。

算法笔记:红黑树

情况1时,调整目标节点B的父节点和叔节点都是红节点,祖父节点为黑节点,我们需要将父节点和叔节点的颜色改成黑色,祖父节点设为红节点,并将调整目标设为祖父节点。

算法笔记:红黑树

情况2情况3中,新插入节点的父节点为红节点,祖父节点为黑节点,并且叔节点为黑节点。首选需要把情况2转换成情况3,让B成为黑节点,A和C为B的红色子节点,并将调整目标设为A。往往在处理完这两种情况后,红黑树完成了调整。

由于NIL也算是黑色节点,所以还需要定义一个获取节点颜色的宏。

调整过程是自下而上的,一个插入的新节点的颜色是红色的,每次调整的目标是使每个子树保持红黑树的性质。对于情况2和3来说,调整结束后子树树根为黑色,对整体的性质不会造成影响。而在情况1中,子树树根为红色,对整体的性质造成了影响,需要继续调整,这就是循环条件的意义

void insertFixup(Node *ptr)
{
    while (ptr->_parent->_color == Node::RED) {
        if (ptr->_parent == ptr->_parent->_parent->_left) {
            Node *y = ptr->_parent->_parent->_right;
            // case 1
            if (y->_color == Node::RED) {
                ptr->_parent->_color = Node::BLACK;
                y->_color = Node::BLACK;
                ptr->_parent->_parent->_color = Node::RED;
                ptr = ptr->_parent->_parent;
            } else {
                // case 2: switch case 2 to case 3
                if (ptr == ptr->_parent->_right) {
                    ptr = ptr->_parent;
                    leftRotate(ptr);
                }
                // case 3
                ptr->_parent->_color = Node::BLACK;
                ptr->_parent->_parent->_color = Node::RED;
                rightRotate(ptr->_parent->_parent);
            }
        } else {
            // with 'left' and 'right' exchanged
            Node *y = ptr->_parent->_parent->_left;
            if (y->_color == Node::RED) {
                ptr->_parent->_color = Node::BLACK;
                y->_color = Node::BLACK;
                ptr->_parent->_parent->_color = Node::RED;
                ptr = ptr->_parent->_parent;
            } else {
                if (ptr == ptr->_parent->_left) {
                    ptr = ptr->_parent;
                    rightRotate(ptr);
                }
                ptr->_parent->_color = Node::BLACK;
                ptr->_parent->_parent->_color = Node::RED;
                leftRotate(ptr->_parent->_parent);
            }
        }
    }
    root->_color = Node::BLACK;
}

删除

删除的过程比插入过程复杂很多。与二叉树一样,我们需要一个替换操作,将子树u替换成子树v。

void transplant(shared_ptr<Node> u, shared_ptr<Node> v)
{
    if (u->_parent == nil)
        root = v;
    else if (u == u->_parent->_left)
        u->_parent->_left = v;
    else
        u->_parent->_right = v;
    v->_parent = u->_parent;
}

删除的过程和二叉树类似,多了一些处理哨兵、记录颜色的过程。

    void remove(Node *ptr)
    {
        Node *y = ptr, *x;
        int y_original_color = y->_color;
        if (y->_left == nil) {
            x = ptr->_right;
            transplant(ptr, ptr->_right);
        } else if (y->_right == nil) {
            x = ptr->_left;
            transplant(ptr, ptr->_left);
        } else {
            y = min(ptr->_right);
            y_original_color = y->_color;
            x = y->_right;
            if (y->_parent == ptr)
                x->_parent = y; // change nil->_parent
            else {
                transplant(y, y->_right);
                y->_right = ptr->_right;
                y->_right->_parent = y;
            }
            transplant(ptr, y);
            y->_left = ptr->_left;
            y->_left->_parent = y;
            y->_color = ptr->_color;
        }
        if (y_original_color == Node::BLACK)
            deleteFixup(x);
    }

首先考虑一下删除节点的时候,我们对红黑树造成了什么样的影响。如果删除一个红色节点,那么红黑树的性质并不会收到任何影响;如果删除的是一个黑色节点,那么意味着黑高相等的性质将不复存在,删除一个黑色节点。那么和插入调整的思路类似,每次调整的目标是保持子树内的性质。

调整过程需要分左右对称的四种情况:

算法笔记:红黑树

  • 情况1:有一个红色的兄弟节点,通过旋转和颜色调换,使红色节点到调整目标节点一侧来,变成情况2、3、4中的一种;
  • 情况2:兄弟节点的两个子节点全为黑,于是把兄弟节点设为红节点,这样一来,子树中的黑高是相等了,但是删除的黑节点并没有被弥补,还需要继续往上调整;
  • 情况3:兄弟节点左红右黑,这个时候需要把红色节点调整到叔节点的右侧,变成情况4;
  • 情况4:兄弟节点右节点为红,这个时候需要把红节点调整到调整目标节点一侧来,用这个红色节点弥补删除的黑色节点。调整结束后,子树满足红黑树性质,结束调整过程。

而对于循环条件。应该怎么理解呢?如果调整过程到了根节点,那么就不存在某子树内黑高缺一的情况,可以结束循环。如果遇到了红节点,那么把这个红节点变成黑节点就可以解决黑高不等的情况。

void removeFixup(Node *ptr)
{
    while (ptr != root && ptr->_color == Node::BLACK) {
        if (ptr == ptr->_parent->_left) {
            Node *w = ptr->_parent->_right;
            // case 1
            if (w->_color == Node::RED) {
                w->_color = Node::BLACK;
                ptr->_parent->_color = Node::RED;
                leftRotate(ptr->_parent);
                w = ptr->_parent->_right;
            }
            // case 2
            if (w->_left->_color == Node::BLACK && w->_right->_color == Node::BLACK) {
                w->_color = Node::RED;
                ptr = ptr->_parent;
            } else {
                // case 3
                if (w->_right->_color == Node::BLACK) {
                    w->_left->_color = Node::BLACK;
                    w->_color = Node::RED;
                    rightRotate(w);
                    w = ptr->_parent->_right;
                }
                // case 4
                w->_color = ptr->_parent->_color;
                ptr->_parent->_color = Node::BLACK;
                w->_right->_color = Node::BLACK;
                leftRotate(ptr->_parent);
                ptr = root;
            }
        } else {
            // with 'left' and 'right' exchanged
            Node *w = ptr->_parent->_left;
            if (w->_color == Node::RED) {
                w->_color = ptr->_parent->_color;
                ptr->_parent->_color = Node::RED;
                rightRotate(ptr->_parent);
                w = ptr->_parent->_left;
            }
            if (w->_left->_color == Node::BLACK && w->_right->_color == Node::BLACK) {
                w->_color = Node::RED;
                ptr = ptr->_parent;
            } else {
                if (w->_left->_color == Node::BLACK) {
                    w->_color = Node::RED;
                    w->_right->_color = Node::BLACK;
                    leftRotate(w);
                    w = ptr->_parent->_left;
                }
                w->_color = ptr->_parent->_color;
                w->_left->_color = Node::BLACK;
                ptr->_parent->_color = Node::BLACK;
                rightRotate(ptr->_parent);
                ptr = root;
            }
        }
    }
    ptr->_color = Node::BLACK;
}

查找

节点颜色对于查找过程没有意义,红黑树查找过程和二叉树是一样的。

收藏
评论区

相关推荐

Java的其他Map
一、LinkedHashMap 1.1 应用场景 HashMap是无序的,当我们希望有顺序地去存储keyvalue时,就需要使用LinkedHashMap了。 1.2 插入顺序和访问顺序 LinkedHashMap默认的构造参数是默认  插入顺序的,就是说你插入的是什么顺序,读出来的就是什么顺序,但是也有访问顺序,就是说你访问了一个key,这个
算法笔记:红黑树
红黑树,一种平衡二叉树,最为著名的应用就是C STL中的map,是有序集合最为理想的存储方式之一。除了二叉树所具有的属性之后,红黑树中每个节点多了一个“颜色”属性,可以是红色或者是黑色。一棵红黑树应该满足一下的性质: 1. 每个节点是红色或者黑色的; 2. 根节点是黑色的; 3. 每个叶节点nil是黑色的(使用哨兵节点在删除调整时可以方便不少); 4. 如
推荐程序员面试秘籍!2021年大厂Java岗面试必问
01 JAVA基础 1.1 java知识点 Hashmap 源码级掌握,扩容,红黑树,最小树化容量,hash冲突解决,有些面试官会提出发自灵魂的审问,比如为什么是红黑树,别的树不可以吗;为什么8的时候树化,4不可以吗,等等 concureentHashMap,段锁,如何分段,和hashmap在hash上的区别,性能,等等 HashTable ,同步锁,这块可
高级java面试题,附答案+考点
蚂蚁金服一面1. 两分钟的自我介绍2. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别3. B 树和 B+树的区别,为什么 MySQL 要使用 B+树4. HashMap 如何解决 Hash 冲突5. epoll 和 poll 的区别,及其应用场景6. 简述线程池原理,FixedThreadPoo
C++面试宝典
**算法与数据结构篇** 1.C++两种map 参考回答: unordered\_map(哈希表)和map(红黑树) [https://blog.csdn.net/zzhang\_12/article/details/81173891](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2
Java 中常见的数据结构
### 1、数据结构有什么作用? 当使用 Java 里面的容器类时,你有没有想过,怎么 ArrayList 就像一个无限扩充的数组,也好像链表之类的。很好使用,这就是数据结构的用处,只不过你在不知不觉中使用了。 数据结构内容比较多,细细的讲解也是相对费功夫的,不可能达到一蹴而就。我就将常见的数据结构:`堆栈、队列、数组、链表和红黑树` 给大家介绍一下,作
Java8 HashMap详解
Java8 HashMap Java8 对 HashMap 进行了一些修改,最大的不同就是利用了红黑树,所以其由 数组+链表+红黑树 组成。 根据 Java7 HashMap 的介绍,我们知道,查找的时候,根据 hash 值我们能够快速定位到数组的具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的
Java并发容器——ConcurrentSkipListMap和ConcurrentHashMap
原文:[http://www.cnblogs.com/ygj0930/p/6543901.html](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2Fwww.cnblogs.com%2Fygj0930%2Fp%2F6543901.html) 一:ConcurrentSkipListMap
Java集合,TreeMap底层实现和原理
概述 == 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加了阅读的难度,虽然是1.7,但是对于1.8做了重大改动的内容,文章也会进行说明。 TreeMap实现了SotredMap接口,它是有序的集合。而且是一个红黑树结构,每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定
java语言基础6
hashmap的数据结构,HashMap的数据结构是数组+链表+红黑树(红黑树since JDK1.8)。我们常把数组中的每一个节点称为一个桶。当向桶中添加一个键值对时,首先计算键值对中key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这种现象称为碰撞,这时按照尾插法(jdk1.7及以前为头插法)的方式添
java集合之HashMap源码解读
源自:jdk1.8.0\_121 `HashMap`继承自`AbstractMap`,实现了`Map`、`Cloneable`、`Serializable`。 > `HashMap`内部是由数组、链表、红黑树实现的 变量 == // 默认大小 static final int DEFAULT_INITIAL_CAPACI
Unity开发——红点系统设计
在开发途中,因为红点的逻辑比较宏观,所以很容易养成开发完功能,到处补红点逻辑的坏习惯,也因此踩过不少坑,这两天撸了下项目的红点系统,顺便自己也写了另一版。 也分享下红点的思路。 ![](https://oscimg.oschina.net/oscnet/f445614bc10bf3bdad68c2dbf9f24eb89ad.png) 首先红点系统的基础
未来的学习目标
> **前言:十大专栏技术点,每一个技术点都有书籍推荐,技术点原理+项目相结合讲解,实现与项目的字眼,都是纯手写代码去实现。** ![在这里插入图片描述](https://static.oschina.net/uploads/img/202012/12144945_GFfT.png) 一:精进基石专栏 -------- **技术点:** **1.1
B+树原理以及Java代码实现
最初查找二叉树,由于树的高度会随着有序序列输入而急剧增长,后来出现平衡二叉树,红黑树。B树可以海量数据的快速查询检索,B树主要分为B树(B-树),B+树,B\*树等。 **B树(B-树)** M路搜索树,参数M定义节点的分支个数; 对于根节点孩子数目为\[2,M\],对于其余节点孩子数目为\[M/2,M\]; 每个节点含有关键字属性,至少M/2-1
HashMap1.7和1.8,红黑树原理!
jdk 1.7 ------- ### 概述 HashMap基于Map接口实现,元素以键值对的方式存储,并允许使用null键和null值,但只能有一个键作为null,因为key不允许重复,另外HashMap不能保证放入元素的数据,它是无序的,和放入的顺序并不能相同,HashMap是线程不安全的。 ### 继承关系 public class H

热门文章

算法笔记:B树分布式系统基石:Paxos

最新文章

算法笔记:B树分布式系统基石:Paxos