【数据结构 08】红黑树

一、概述

红黑树，是一种二叉搜索树，每一个节点上有一个存储位表示节点的颜色，可以是Red或Black。

通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长上两倍，因而是接进平衡的。

红黑树性质：

• 根节点是黑色
• 红节点的两个孩子一定是黑色的；黑节点的两个孩子不一定是红色的。没有连续的红节点
• 对于每个节点，从该节点到其后所有后代叶节点的简单路径上，均包含相同数目的黑节点
• 每个叶子节点都是黑色的（NIL空节点）

二、算法

红黑树在设计的时候，插入策略与AVL树一样，只是插入之后的调整策略与AVL不同（旋转策略是一样的，但是红黑树需要考虑变色且无需再考虑平衡因子）

只看遍历的时间复杂度的话，AVL树的时间复杂度是低于红黑树的，因为AVL树的时间复杂度是无限接近于，而红黑树的时间复杂度是 ~，但这在系统层面的时间损失很小。

从调整策略的角度，红黑树的调整次数与旋转次数都远低于AVL树。所以综合来看，红黑树的性能是优于AVL树的，map和set的底层封装的也正是红黑树。

三、调整策略

红黑树的根节点一定是黑色，新插入的节点默认为是红色。

当新插入一个红色节点cur时，先观察cur的父节点parent，如果父节点是黑色，则无需调整；如果父节点也是红节点，那么再观察cur节点的叔叔节点uncle，根据uncle节点的情况进行调整。

红黑树调整策略的核心思路：不能出现连续的红色节点，每条路径的黑色节点数量一样

调整策略分为三种情况：

• 情况1：父节点parent和叔叔节点uncle都是红色，此时只需变色调整，不需旋转，并向上调整
• 情况2：父节点parent为红色，叔叔节点不存在或为黑色，cur节点和parent节点都同为左节点或同为右节点，此时需要左单旋或者右单旋，无需向上调整
• 情况3：父节点parent为红色，叔叔节点不存在或为黑色，cur节点为左节点时parent节点为右节点，或者cur节点为右节点时parent节点为左节点，此时需要左右双旋或者右左双旋，无需向上调整

情况1：parent节点是红色，uncle节点也是红色

调整方法：parent节点与uncle节点变为黑色，祖父节点grandparent节点变为红色，然后将cur变为祖父节点，parent节点依然为cur节点的父节点，向上调整，直到出现parent节点为空，最后再将根节点置为黑色。

如图：

情况1

 

情况1

情况2： 父节点parent为红色，叔叔节点不存在或为黑色，cur节点和parent节点都同为左节点或同为右节点

调整方法：以祖父节点grandparent为轴点进行左单旋或则右单旋，父节点变成黑色，祖父节点变成红色。

如图：

情况2

情况1 情况2 结合调整

情况3：父节点parent为红色，叔叔节点不存在或为黑色，cur节点为左节点时parent节点为右节点，或者cur节点为右节点时parent节点为左节点

调整方法：先以parent节点为轴心进行左单旋或者右单旋，再以grandparent节点为轴心进行与上一步操作相反的单旋，最后将cur节点变成黑色，将grandparent节点变为红色

示例：将数列{ 16, 3, 7, 9, 26, 18, 14, 15, 13, 11 }按顺序插入红黑色中

图1 插入16、3、7

图2 插入9

图3 插入26、18

图4 插入14、15

图5 插入13

图6 插入11

四、RBTree.h

#define _CRT_SECURE_NO_WARNINGS 1#pragma once
#include <iostream>enum Color
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{std::pair<K, V> kv;RBTreeNode* parent;RBTreeNode* left;RBTreeNode* right;Color col;RBTreeNode(const std::pair<K, V>& x): kv(x), parent(nullptr), left(nullptr), right(nullptr), col(RED){}
};template<class K, class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const std::pair<K, V>& x){if (_root == nullptr){_root = new Node(x);_root->col = BLACK;return true;}// 寻找新节点该插入的位置Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->kv.first > x.first)cur = cur->left;else if (cur->kv.first < x.first)cur = cur->right;elsereturn false;}// 创建新节点cur = new Node(x);cur->parent = parent;if (parent->kv.first > x.first)parent->left = cur;elseparent->right = cur;// 调整颜色while (parent && parent->col == RED){Node* grandpa = parent->parent;if (grandpa->left == parent){Node* uncle = grandpa->right;if (uncle && uncle->col == RED){// 情况1，变色parent->col = uncle->col = BLACK;grandpa->col = RED;cur = grandpa;parent = cur->parent;}else{if (parent->left == cur){// 情况2，右单旋_RotateRight(grandpa);parent->col = BLACK;grandpa->col = RED;}else{// 情况3，左右双旋_RotateLeft(parent);_RotateRight(grandpa);cur->col = BLACK;grandpa->col = RED;}break;}}else{Node* uncle = grandpa->left;if (uncle && uncle->col == RED){// 情况1，变色parent->col = uncle->col = BLACK;grandpa->col = RED;cur = grandpa;parent = cur->parent;}else{if (parent->right == cur){// 情况2，左单旋_RotateLeft(grandpa);parent->col = BLACK;grandpa->col = RED;}else{// 情况3，右左双旋_RotateRight(parent);_RotateLeft(grandpa);cur->col = BLACK;grandpa->col = RED;}break;}}}_root->col = BLACK;return true;}void InOrder(){_InOrder(_root);std::cout << std::endl;}bool IsBalance(){if (_root == nullptr)return true;if (_root->col == RED)return false;// 计算最左路径上的黑节点数量int ref = 0;Node* left = _root;while (left){if (left->col == BLACK)++ref;left = left->left;}return _IsBalance(_root, 0, ref);}private:void _RotateLeft(Node* parent){Node* subR = parent->right;Node* subRL = subR->left;parent->right = subRL;if (subRL)subRL->parent = parent;subR->left = parent;Node* ppNode = parent->parent;parent->parent = subR;if (ppNode == nullptr){_root = subR;subR->parent = nullptr;}else{if (ppNode->left == parent)ppNode->left = subR;elseppNode->right = subR;subR->parent = ppNode;}}void _RotateRight(Node* parent){Node* subL = parent->left;Node* subLR = subL->right;parent->left = subLR;if (subLR)subLR->parent = parent;subL->right = parent;Node* ppNode = parent->parent;parent->parent = subL;if (ppNode == nullptr){_root = subL;subL->parent = nullptr;}else{if (ppNode->left == parent)ppNode->left = subL;elseppNode->right = subL;subL->parent = ppNode;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->left);std::cout << "<" << root->kv.first << "," << root->kv.second << "> ";_InOrder(root->right);}bool _IsBalance(Node* root, int blackNum, int ref){if (root == nullptr){if (blackNum != ref){std::cout << "路径黑色节点数量不相等" << std::endl;return false;}return true;}if (root->col == RED && root->parent->col == RED){std::cout << "路径出现连续红节点" << "<" << root->kv.first << "," << root->kv.second << "> " << std::endl;return false;}if (root->col == BLACK)++blackNum;return _IsBalance(root->left, blackNum, ref)&& _IsBalance(root->right, blackNum, ref);}private:Node* _root = nullptr;
};

五、test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include "RBTree.h"
#include <ctime>void test1_RBTree()
{int arr[] = { 16, 3, 7, 9, 26, 18, 14, 15, 13, 11 };//int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };RBTree<int, int> t;for (auto& e : arr){t.Insert(std::make_pair(e, e));}t.InOrder();std::cout << std::endl;std::cout << t.IsBalance() << std::endl;
}void test2_RBTree()
{RBTree<int, int> t;for (int i = 0; i < 100000; ++i){int x = rand() % 10000;t.Insert(std::make_pair(x, x));}t.InOrder();std::cout << std::endl;std::cout << t.IsBalance() << std::endl;
}int main()
{srand(time(nullptr));test1_RBTree();//test2_RBTree();return 0;
}