HelloWorld
登录

算法笔记：红黑树

zhenghaoz

2021-03-13

2213 0 0

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

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

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

1struct Node {
2    enum Color { RED, BLACK };
3    Color _color;
4    Key _key;
5    Value _value;
6    Node *_parent, *_left, *_right;
7    Node(): _color(BLACK) {}
8    Node(const Key &key, const Value &value, Node *left, Node *right, Node *parent):
9        _key(key), _value(value), _color(RED), _left(left), _right(right), _parent(parent) {}
10};

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

<!--more-->

旋转

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

tree-rotation

以左旋为例，操作可以分为三步：

  1. 将Q的左子节点变成P的右子节点；
  2. 将P变成Q的左子节点；
  3. 将Q变成当前子树的根节点。
1void leftRotate(Node *x)
2{
3    Node *y = x->_right;
4    // remove y->left to x->right
5    x->_right = y->_left;
6    if (x->_right != nil)
7        x->_right->_parent = x;
8    // remove y up
9    y->_parent = x->_parent;
10    if (x->_parent == nil)
11        root = y;
12    else if (x->_parent->_left == x)
13        x->_parent->_left = y;
14    else
15        x->_parent->_right = y;
16    // remove x down
17    x->_parent = y;
18    y->_left = x;
19}

插入

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

1void insert(Node *nptr)
2{
3    Node *it = root, *p = root;
4    // find insert position
5    while (it != nil) {
6        p = it;
7        if (nptr->_key < it->_key)
8            it = it->_left;
9        else if (nptr->_key > it->_key)
10            it = it->_right;
11        else {
12            // find target key-value
13            it->_value = nptr->_value;
14            return;
15        }
16    }
17    // insert
18    nptr->_parent = p;
19    if (p == nil)
20        root = nptr;
21    else if (nptr->_key < p->_key)
22        p->_left = nptr;
23    else
24        p->_right = nptr;
25    // fixup
26    insertFixup(nptr);
27}

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

insert-fixup-1

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

insert-fixup-2

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

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

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

1void insertFixup(Node *ptr)
2{
3    while (ptr->_parent->_color == Node::RED) {
4        if (ptr->_parent == ptr->_parent->_parent->_left) {
5            Node *y = ptr->_parent->_parent->_right;
6            // case 1
7            if (y->_color == Node::RED) {
8                ptr->_parent->_color = Node::BLACK;
9                y->_color = Node::BLACK;
10                ptr->_parent->_parent->_color = Node::RED;
11                ptr = ptr->_parent->_parent;
12            } else {
13                // case 2: switch case 2 to case 3
14                if (ptr == ptr->_parent->_right) {
15                    ptr = ptr->_parent;
16                    leftRotate(ptr);
17                }
18                // case 3
19                ptr->_parent->_color = Node::BLACK;
20                ptr->_parent->_parent->_color = Node::RED;
21                rightRotate(ptr->_parent->_parent);
22            }
23        } else {
24            // with 'left' and 'right' exchanged
25            Node *y = ptr->_parent->_parent->_left;
26            if (y->_color == Node::RED) {
27                ptr->_parent->_color = Node::BLACK;
28                y->_color = Node::BLACK;
29                ptr->_parent->_parent->_color = Node::RED;
30                ptr = ptr->_parent->_parent;
31            } else {
32                if (ptr == ptr->_parent->_left) {
33                    ptr = ptr->_parent;
34                    rightRotate(ptr);
35                }
36                ptr->_parent->_color = Node::BLACK;
37                ptr->_parent->_parent->_color = Node::RED;
38                leftRotate(ptr->_parent->_parent);
39            }
40        }
41    }
42    root->_color = Node::BLACK;
43}

删除

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

1void transplant(shared_ptr<Node> u, shared_ptr<Node> v)
2{
3    if (u->_parent == nil)
4        root = v;
5    else if (u == u->_parent->_left)
6        u->_parent->_left = v;
7    else
8        u->_parent->_right = v;
9    v->_parent = u->_parent;
10}

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

1    void remove(Node *ptr)
2    {
3        Node *y = ptr, *x;
4        int y_original_color = y->_color;
5        if (y->_left == nil) {
6            x = ptr->_right;
7            transplant(ptr, ptr->_right);
8        } else if (y->_right == nil) {
9            x = ptr->_left;
10            transplant(ptr, ptr->_left);
11        } else {
12            y = min(ptr->_right);
13            y_original_color = y->_color;
14            x = y->_right;
15            if (y->_parent == ptr)
16                x->_parent = y; // change nil->_parent
17            else {
18                transplant(y, y->_right);
19                y->_right = ptr->_right;
20                y->_right->_parent = y;
21            }
22            transplant(ptr, y);
23            y->_left = ptr->_left;
24            y->_left->_parent = y;
25            y->_color = ptr->_color;
26        }
27        if (y_original_color == Node::BLACK)
28            deleteFixup(x);
29    }

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

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

delete-fixup

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

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

1void removeFixup(Node *ptr)
2{
3    while (ptr != root && ptr->_color == Node::BLACK) {
4        if (ptr == ptr->_parent->_left) {
5            Node *w = ptr->_parent->_right;
6            // case 1
7            if (w->_color == Node::RED) {
8                w->_color = Node::BLACK;
9                ptr->_parent->_color = Node::RED;
10                leftRotate(ptr->_parent);
11                w = ptr->_parent->_right;
12            }
13            // case 2
14            if (w->_left->_color == Node::BLACK && w->_right->_color == Node::BLACK) {
15                w->_color = Node::RED;
16                ptr = ptr->_parent;
17            } else {
18                // case 3
19                if (w->_right->_color == Node::BLACK) {
20                    w->_left->_color = Node::BLACK;
21                    w->_color = Node::RED;
22                    rightRotate(w);
23                    w = ptr->_parent->_right;
24                }
25                // case 4
26                w->_color = ptr->_parent->_color;
27                ptr->_parent->_color = Node::BLACK;
28                w->_right->_color = Node::BLACK;
29                leftRotate(ptr->_parent);
30                ptr = root;
31            }
32        } else {
33            // with 'left' and 'right' exchanged
34            Node *w = ptr->_parent->_left;
35            if (w->_color == Node::RED) {
36                w->_color = ptr->_parent->_color;
37                ptr->_parent->_color = Node::RED;
38                rightRotate(ptr->_parent);
39                w = ptr->_parent->_left;
40            }
41            if (w->_left->_color == Node::BLACK && w->_right->_color == Node::BLACK) {
42                w->_color = Node::RED;
43                ptr = ptr->_parent;
44            } else {
45                if (w->_left->_color == Node::BLACK) {
46                    w->_color = Node::RED;
47                    w->_right->_color = Node::BLACK;
48                    leftRotate(w);
49                    w = ptr->_parent->_left;
50                }
51                w->_color = ptr->_parent->_color;
52                w->_left->_color = Node::BLACK;
53                ptr->_parent->_color = Node::BLACK;
54                rightRotate(ptr->_parent);
55                ptr = root;
56            }
57        }
58    }
59    ptr->_color = Node::BLACK;
60}

查找

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

点赞
收藏

评论区

加载中...

相关推荐

java语言基础6

hashmap的数据结构，HashMap的数据结构是数组链表红黑树（红黑树sinceJDK1.8）。我们常把数组中的每一个节点称为一个桶。当向桶中添加一个键值对时，首先计算键值对中key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这种现象称为碰撞，这时按照尾插法(jdk1.7及以前为头插法)的方式添

推荐程序员面试秘籍！2021年大厂Java岗面试必问

01JAVA基础1.1java知识点Hashmap源码级掌握，扩容，红黑树，最小树化容量，hash冲突解决，有些面试官会提出发自灵魂的审问，比如为什么是红黑树，别的树不可以吗；为什么8的时候树化，4不可以吗，等等concureentHashMap，段锁，如何分段，和hashmap在hash上的区别，性能，等等HashTable，同步锁，这块可

大厂Java初级开发工程师！！！面试必问项之Set实现类：TreeSet

一、TreeSet概述1、TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。2、TreeSet顾名思义他内部维护的是一个TreeMap，底层是红黑二叉树，他使得集合内都是有序的序列。　　3、Tree可以按照添加对象的指定属性，进行排序，所以向TreeSet中添加的数据，要求是相同类的对象。4、两

高级java面试题，附答案+考点

蚂蚁金服一面1.两分钟的自我介绍2.二叉搜索树和平衡二叉树有什么关系，强平衡二叉树（AVL树）和弱平衡二叉树（红黑树）有什么区别3.B树和B树的区别，为什么MySQL要使用B树4.HashMap如何解决Hash冲突5.epoll和poll的区别，及其应用场景6.简述线程池原理，FixedThreadPoo

B+树原理以及Java代码实现

最初查找二叉树，由于树的高度会随着有序序列输入而急剧增长，后来出现平衡二叉树，红黑树。B树可以海量数据的快速查询检索，B树主要分为B树（B树），B树，B\树等。B树（B树）M路搜索树，参数M定义节点的分支个数；对于根节点孩子数目为\2,M\，对于其余节点孩子数目为\M/2,M\;每个节点含有关键字属性，至少M/21

Java集合，TreeMap底层实现和原理

概述文章的内容基于JDK1.7进行分析，之所以选用这个版本，是因为1.8的有些类做了改动，增加了阅读的难度，虽然是1.7，但是对于1.8做了重大改动的内容，文章也会进行说明。TreeMap实现了SotredMap接口，它是有序的集合。而且是一个红黑树结构，每个keyvalue都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定