红黑树

千次阅读 多人点赞

2022-03-26 18:13:48

C++红黑树

零、前言
一、红黑树的概念及性质
二、红黑树结点的定义
三、红黑树的插入操作
四、红黑树的验证
五、红黑树的删除
六、红黑树与**AVL**树的比较

零、前言

本章继AVL树后继续讲解学习C++中另一个二叉搜索树–红黑树

一、红黑树的概念及性质

概念：

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black

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

注：AVL树是严格平衡的二叉搜索树，左右子树高度不超过1；红黑树是近似平衡，最长路径不超过最短路径的二倍

示图：

红黑树的性质：

每个结点不是红色就是黑色

根节点是黑色的

如果一个节点是红色的，则它的两个孩子结点是黑色的

对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点

每个NIL结点都是黑色的(此处的结点指的是空结点)（该条规则确定了路径条数）

为什么红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍：

红黑树第三条性质说明红黑树不能存在连续（父子相连）的红结点，可以存在连续的黑结点，又由于第四条性质每个路径上的黑结点个数都相同，所以对于最短路径来说一定是都是黑色结点，对于最长路径来说一定是黑色红色相间的路径，所以最长路径不超过最短路径长度的二倍

示图：

二、红黑树结点的定义

对于红黑树来说以颜色来代替AVL树的平衡因子的作用，除此之外在定义上没有什么区别

实现代码：

enum Colour//颜色
{
	RED,
	BLACK,
};
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

注：此处采用枚举来表示，当然也可以使用其他方式

在节点的定义中为什么要将节点的默认颜色给成红色的：

如果默认颜色为黑，那么在插入中插入一个黑结点一定会让该路径上的黑结点数量加1，从而与其他路径上黑结点数量造成不一致，而一定会影响该棵红黑树

如果默认颜色为红，那么在插入中插入一个红结点，可能新插入结点的父结点为黑色结点则没有影响，也可能新插入结点的父结点为红结点，由于不能存在连续的（父子相连的）红色结点，而对该棵树造成影响

所以默认为红色比较黑色来说是好的

三、红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，当违反限制条件时就需要做出相应的调整

红黑树的插入可分为两步：

按照二叉搜索的树规则插入新节点

新节点插入后检查红黑树的性质是否造到破坏

注意：

因为新节点的默认颜色是红色，如果其父亲节点的颜色是黑色，则没有违反红黑树任何性质，则不需要调整

当新插入节点的父亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论

因为插入结点的父结点是红色的，说明父结点不是根结点（根结点是黑色的），因此插入结点的祖父结点（父结点的父结点）就一定存在

红黑树调整时具体应该如何调整，主要是看插入结点的叔叔（插入结点的父结点的兄弟结点），根据插入结点叔叔的不同，可将红黑树的调整分为三种情况

注：约定cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

1、变色处理

情况一: cur为红，p为红，g为黑，u存在且为红

示图：

分析：

为了让该以 g 为根的子树不存在连续的红色结点，并且不增加路径上的黑色结点，我们让 g 的颜色变红，让 u 和 p 的颜色变黑，各路径上黑色结点数量没变，以此达到红黑树的性质

因为 p 和 u 的颜色变黑，对其子树没有影响，但是 g 的颜色变红，可能存在影响，需要继续向上判断

判断逻辑：

如果 g 就是该棵树的根那么最后需要将 g 的颜色变黑

如果 g 是整棵树的子树，如果 g 的父节点是是黑色结点则不用调整，如果是红色结点则需要根据具体情况来做出调整

解决方式：

将p,u改为黑，g改为红，然后把g当成cur，继续向上调整

抽象示图：

动图演示1：

动图演示2：

2、单旋+变色

情况二: cur为红，p为红，g为黑，u不存在**/u**为黑

示图：

分析：

当 u 节点不存在时，说明cur一定是插入节点，如果 cur 不是新插入节点，那么在插入前时 cur 一定是黑色结点（由黑色变红），则插入前就不符合路径上黑结点数量相同的性质

当 u 节点存在且为黑色时，说明 cur 的颜色插入前一定是黑色，进过插入后变色为红色，否则在插入前就存在连续的红色结点，不符合红黑树性质

解决方法：

如果p为g的左孩子，cur为p的左孩子，则进行右单旋转，p变黑，g变红

如果p为g的右孩子，cur为p的右孩子，则进行左单旋转，p变黑，g变红

抽象示图：

动态示图：

动图演示2：

3、双旋+变色

情况三: cur为红，p为红，g为黑，u不存在**/u**为黑

示图：

分析：

这里显然一次旋转也无法让达到红黑树平衡，由此就需要进行两次旋转

解决方式：

如果p为g的左孩子，cur为p的右孩子，则针对p做左单旋转，p旋转后再对g进行右单旋，旋转后将cur变黑，g变红

如果p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，p旋转后再对g进行左单旋，旋转后将cur变黑，g变红

抽象示图：

动图演示1：

动图演示2：

4、插入实现

插入主体实现：

pair<Node*, bool> Insert(const pair<K, V>& kv)
{
    //空树的情况
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;
        return make_pair(_root, true);
    }

    //查找位置插入节点
    Node* cur = _root, * parent = _root;
    while (cur)
    {
        if (cur->_kv.first > kv.first)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_kv.first < kv.first)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return make_pair(cur, false);
        }
    }

    //创建链接节点
    cur = new Node(kv);
    Node* newnode = cur;
    if (parent->_kv.first > kv.first)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    cur->_parent = parent;
    
    //父节点存在且为红，则需要调整（不能存在连续的红色节点）
    while (parent && parent->_col == RED)
    {
        //此时当前节点一定有祖父节点
        Node* granparent = parent->_parent;
        //具体调整情况主要看叔叔节点
        //分左右讨论
        if (parent == granparent->_left)
        {
            Node* uncle = granparent->_right;
            //情况1：叔叔节点存在且为红
            if (uncle && uncle->_col == RED)
            {
                //修改颜色，继续向上检查
                granparent->_col = RED;
                parent->_col = uncle->_col = BLACK;

                cur = granparent;
                parent = cur->_parent;
            }
            else//情况2和3：叔叔节点不存在 或者存在且为黑
            {
                //单旋(三代节点为斜线)+变色
                if (cur == parent->_left)
                {
                    RotateR(granparent);

                    granparent->_col = RED;
                    parent->_col = BLACK;
                }
                else//双旋(三代节点为折线)+变色
                {
                    RotateL(parent);
                    RotateR(granparent);

                    cur->_col = BLACK;
                    granparent->_col = RED;
                }
                //旋转后不需再向上调整了
                break;
            }
        }
        else//parent=grandparent->right
        {
            Node* uncle = granparent->_left;
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                granparent->_col = RED;

                cur = granparent;
                parent = cur->_parent;
            }
            else
            {
                if (cur == parent->_right)
                {
                    RotateL(granparent);

                    parent->_col = BLACK;
                    granparent->_col = RED;
                }
                else
                {
                    RotateR(parent);
                    RotateL(granparent);

                    cur->_col = BLACK;
                    granparent->_col = RED;
                }
                break;
            }
        }
    }
    
    //确保根节点为黑
    _root->_col = BLACK;
    return make_pair(newnode, true);
}

旋转实现：

void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    Node* parentP = parent->_parent;


    parent->_right = subRL;
    if (subRL)
    {
        subRL->_parent = parent;
    }

    subR->_left = parent;
    parent->_parent = subR;

    if (parent == _root)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        subR->_parent = parentP;
        if (parentP->_left == parent)
        {
            parentP->_left = subR;
        }
        else
        {
            parentP->_right = subR;
        }
    }
}

void RotateR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* parentP = parent->_parent;


    parent->_left = subLR;
    if (subLR)
    {
        subLR->_parent = parent;
    }

    subL->_right = parent;
    parent->_parent = subL;

    if (parent == _root)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        subL->_parent = parentP;
        if (parentP->_left == parent)
        {
            parentP->_left = subL;
        }
        else
        {
            parentP->_right = subL;
        }
    }
}

四、红黑树的验证

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)

检测其是否满足红黑树的性质

实现代码：

bool IsRBTree()
{
    //空树
    if (_root == nullptr)
    {
        return true;
    }
    //根节点为黑色
    if (_root->_col == RED)
    {
        cout << "根节点为红色" << endl;
        return false;
    }
    //黑色结点数量各路径上相同
    //先走一条得到基准值
    int Blacknum = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK)
            Blacknum++;
        cur = cur->_left;
    }
    //检查子树
    int i = 0;
    return _IsRBTree(_root, Blacknum, i);
}

bool _IsRBTree(Node* root, int blacknum, int count)
{
    //递归到空节点
    if (root == nullptr)
    {
        if (blacknum == count)
            return true;
        cout << "各路径上黑色节点个数不同" << endl;
        return false;
    }
	//子节点为红则检查父节点是否为红（通过父节点检查子节点会遇到空节点）
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << "存在连续红色节点" << endl;
        return false;
    }
	//计数黑结点
    if (root->_col == BLACK)
        count++;
	//递归左右子树
    return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
}

五、红黑树的删除

红黑树的删除不做讲解，有兴趣可参考：《算法导论》或者《STL源码剖析》
http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
http://blog.csdn.net/chenhuajie123/article/details/11951777

六、红黑树与AVL树的比较

分析总结：

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( )

红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数

所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多

附上源码
RBTree.h:

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

//颜色
enum Colour
{
	RED,
	BLACK,
};
template<class K, class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	RBTree()
		:_root(nullptr)
	{
	}

	void _Destory(Node*& root)
	{
		if (root == nullptr)
			return;

		_Destory(root->_left);
		_Destory(root->_right);

		delete root;
		root = nullptr;
	}
	~RBTree()
	{
		_Destory(_root);
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

	pair<Node*, bool> Insert(const pair<K, V>& kv)
	{
		//空树的情况
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return make_pair(_root, true);
		}

		//查找位置插入节点
		Node* cur = _root, * parent = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return make_pair(cur, false);
			}
		}

		//创建链接节点
		cur = new Node(kv);
		Node* newnode = cur;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//父节点存在且为红，则需要调整（不能存在连续的红色节点）
		while (parent && parent->_col == RED)
		{
			//此时当前节点一定有祖父节点
			Node* granparent = parent->_parent;
			//具体调整情况主要看叔叔节点
			//分左右讨论
			if (parent == granparent->_left)
			{
				Node* uncle = granparent->_right;
				//情况1：叔叔节点存在且为红
				if (uncle && uncle->_col == RED)
				{
					//修改颜色，继续向上检查
					granparent->_col = RED;
					parent->_col = uncle->_col = BLACK;

					cur = granparent;
					parent = cur->_parent;
				}
				else//情况2和3：叔叔节点不存在 或者存在且为黑
				{
					//单旋(三代节点为斜线)+变色
					if (cur == parent->_left)
					{
						RotateR(granparent);

						granparent->_col = RED;
						parent->_col = BLACK;
					}
					else//双旋(三代节点为折线)+变色
					{
						RotateL(parent);
						RotateR(granparent);

						cur->_col = BLACK;
						granparent->_col = RED;
					}
					//旋转后不需再向上调整了
					break;
				}
			}
			else//parent=grandparent->right
			{
				Node* uncle = granparent->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					granparent->_col = RED;

					cur = granparent;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(granparent);

						parent->_col = BLACK;
						granparent->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(granparent);

						cur->_col = BLACK;
						granparent->_col = RED;
					}
					break;
				}
			}
		}

		//确保根节点为黑
		_root->_col = BLACK;
		return make_pair(newnode, true);
	}

	bool IsRBTree()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col == RED)
		{
			cout << "根节点为红色" << endl;
			return false;
		}

		int Blacknum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				Blacknum++;
			cur = cur->_left;
		}

		int i = 0;
		return _IsRBTree(_root, Blacknum, i);
	}

private:
	bool _IsRBTree(Node* root, int blacknum, int count)
	{
		if (root == nullptr)
		{
			if (blacknum == count)
				return true;
			cout << "各路径上黑色节点个数不同" << endl;
			return false;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在连续红色节点" << endl;
			return false;
		}

		if (root->_col == BLACK)
			count++;

		return _IsRBTree(root->_left, blacknum, count) && _IsRBTree(root->_right, blacknum, count);
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* parentP = parent->_parent;


		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		subR->_left = parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			subR->_parent = parentP;
			if (parentP->_left == parent)
			{
				parentP->_left = subR;
			}
			else
			{
				parentP->_right = subR;
			}
		}
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* parentP = parent->_parent;


		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			subL->_parent = parentP;
			if (parentP->_left == parent)
			{
				parentP->_left = subL;
			}
			else
			{
				parentP->_right = subL;
			}
		}
	}

private:
	Node* _root;
};

test.cpp:

#define _CRT_SECURE_NO_WARNINGS 1
#include "RBTree.h"
#include <vector>
#include <string>
#include <stdlib.h>
#include <time.h>

void TestRBTree()
{
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;
	int n = 1000000;
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		int e = rand();
		t.Insert(make_pair(e, e));
	}

	//t.InOrder();
	cout << t.IsRBTree() << endl;
}
void test_RBTree()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	RBTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));

	}
	cout << t.IsRBTree() << endl;
}
int main()
{
    test_RBTree();
	TestRBTree();
	return 0;
}

c++ 红黑树

更多相关内容

HashMap的工作原理和底层实现（二）红黑树的左旋、右旋
2021-01-07 07:27:08

HashMap中的红黑树左旋、右旋摘要: HashMap是java最常用的容器之一，本文会通过阅读源码的方式来理解HashMap中是如何进行红黑树的左旋和右旋一、什么是左旋和右旋 红黑树的性质每个节点要么是黑色，要么...

收起
控制台打印红黑树.rar
2021-05-17 10:29:35

控制台打印红黑树

收起
(001)HashMap之链表转红黑树-treefyBin方法.docx
2020-06-17 10:37:59

详细解读了HashMap中链表转红黑树的treefyBin方法，该方法中涉及到的诸如：replacementTreeNode方法、treeify方法、comparableClassFor方法、compareComparables方法、tieBreakOrder方法、balanceInsertion方法、...

收起
C语言实现红黑树的实例代码
2020-12-25 21:19:44

因为看内核的时候感觉红黑树挺有意思的，所以利用周末的时间来实现一下玩玩。红黑树的操作主要是插入和删除，而删除的时候需要考虑的情况更多一些。具体的操作就不在这里罗嗦了，百度文库里面有一个比较有好的文章，...

收起
高级数据结构—B树、红黑树 python实现
2021-01-20 02:27:24

B树一棵 2t (t>=2)阶（此处阶数表示每个节点最大的孩子数量）B树是一棵平衡的 2t 路搜索树。它或者是空树，或者是满足下列性质的树： 1、根节点至少有两个子女； 2、每个非根节点所包含的关键字个数j满足：t-1<=...

收起
从2-3树理解红黑树
2019-02-25 19:14:19

从2-3树理解红黑树的ppt，包括概念，原理，插入、删除、转换等。

收起
数据结构 红黑树的详解
2021-01-20 06:59:30

数据结构 红黑树的详解 红黑树是具有下列着色性质的二叉查找树： 1.每一个节点或者着红色，或者着黑色。 2.根是黑色的。 3.如果一个节点是红色的，那么它的子节点必须是黑色。 4.从一个节点到一个NULL指针的每一条...

收起
数据结构之红黑树详解
2020-12-31 06:02:30

在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。它是复杂的，但它的操作有着良好的最坏情况运行...

收起
Java-Red-Black-Tree:Java中通用红黑树的实现
2021-06-11 18:18:06

Java-红-黑-树 Java 1.7 中红黑树的实现此代码扩展自 Mark Allen Weiss 在和维基百科（特别是移除操作）

收起

Java
红黑树详解
2017-09-02 15:45:29

红黑树详解（带目录源码）本文适合那些有对二叉树有一定的基础，并且熟悉C语言的读者。本文最主要的参考资料是《Introduction to Algorithms 3rd Edition》。

收起

红黑树
红黑树代码
2018-03-30 16:27:59

红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树...

收起

红黑树
红黑树插入时的自平衡
2020-12-21 16:06:06

红黑树插入时的自平衡 红黑树实质上是一棵自平衡的二叉查找树，引入带颜色的节点也是为了方便在进行插入或删除操作时，如果破坏了二叉查找树的平衡性能通过一系列变换保持平衡。 红黑树的性质每个节点要么是红色，...

收起
红黑树RBT.cpp
2020-05-07 20:18:53

红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 [1] 红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-...

收起
红黑树：红黑树的Matlab实现-matlab开发
2021-05-30 19:08:32

RedBlack树的Matlab使用面向对象的编程方法实现。实现以下方法：树的构造函数添加新节点从树中删除节点画树在树中找到最小条目在树中找到最大条目在树中搜索条目 k。

收起

matlab
AVL和红黑树性能对比
2020-03-17 16:33:22

AVL和红黑树性能对比，有详细的测试数据。AVL和红黑树都是平衡树。 Binary search tree (BST) based data structures, such as AVL trees, red-black trees, and splay trees, are often used in system software...

收起

AVL 红黑树
红黑树可运行代码C++ 使用无父指针的节点构造
2021-01-08 02:44:13

C++实现仅有孩子节点的红黑树 在旋转时用栈存储叔叔父亲祖先等等。支持基本的插删查。使用该红黑树编写的Map通过部分OJ，未发现bug。 /* 此版本无父指针，旋转时用栈确定祖先。使用该红黑树编写的Map通过部分OJ，...

收起
红黑树 一张导图解决红黑树全部插入和删除问题包含详细操作原理情况对比.zip
2021-08-11 10:16:01

红黑树 一张导图解决红黑树全部插入和删除问题包含详细操作原理情况对比

收起
红黑树的插入详细图解，直接拿下红黑树
2022-08-17 17:14:39

红黑树（Red Black Tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）...

收起
红黑树算法C语言实现
2019-03-02 22:07:05

实验1：实现红黑树的基本算法，对n的取值分别为 12、24、36、48、60，随机生成n 个互异的正整数（K1, K2, K3, ……, Kn）作为节点的关键字，向一棵初始空的红黑树中依次插入这n 个节点，统计算法运行所需时间，画...

收起

红黑树
易语言-红黑树模块
2021-07-02 03:48:54

易语言红黑树模块源码例程程序结合汇编代码，实现红黑树结构操作。点评：红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 my小黑

收起
解析红黑树（ppt文档）.ppt
2022-03-01 00:25:21

解析红黑树（ppt文档）.ppt

收起

红黑树
红黑树原理详解
2016-06-07 11:14:21

红黑树性质: 1. 每个结点或红或黑。 2. 根结点为黑色。 3. 每个叶结点(实际上就是NULL指针)都是黑色的。 4. 如果一个结点是红色的,那么它的周边3个节点都是黑色的。 5. 对于每个结点,从该结点到其所有子孙叶结点的...

收起

红黑树
图解红黑树及Java进行红黑二叉树遍历的方法
2020-09-02 08:05:09

红黑树问题是各大计算机考研命题以及面试算法题目中的热门,接下来我们为大家图解红黑树及Java进行红黑二叉树遍历的方法,需要的朋友可以参考下

收起
高级数据结构和算法 红黑树及线段树.ppt
2020-08-08 03:55:38

红黑树及线段树高级算法与数据结构 8红黑树及线段树 8红黑树及线段树 8红黑树及线段树 红黑树(RB树) 棵红黑树本身是一棵二叉排序树且满足下列性质 (1)每一个结点必须是红或黑两者之一; (2)所有叶子结点是黑色的; ...

收起
硬核图解面试最怕的红黑树【建议反复摩擦】
万次阅读 多人点赞 2020-11-05 09:26:58
算法4中给出的红黑树是基于2-3树实现，而且这种实现的红黑树十分特殊，它要求概念模型中的3节点在红黑树中必须用左倾的红色节点来表示。这种限定能够很大的减少红黑树调整过程中的复杂性，我们将在接下来的内容中...
有情怀，有干货，微信搜索【三太子敖丙】关注这个不一样的程序员。

本文 GitHub https://github.com/JavaFamily 已收录，有一线大厂面试完整考点、资料以及我的系列文章。

注：本文比较硬核但是很值得大家花心思看完，看完你一定会有所收获的

红黑树是面试中一个很经典也很有难度的知识点，网传字节跳动面试官最喜欢问这个问题。很多人会觉得这个知识点太难，不想花太多功夫去了解，也有人会认为这个数据结构在日常开发中使用的很少，因此没必要多做掌握。

在此我针对以上两个观点做出一些纠正：首先，红黑树这个数据结构确实复杂，但是还没有到完全无法理解的地步。网上大多博客都不能够清晰完整的描述出红黑树的整个体系，对于红黑平衡调整的细节部分也没有很详尽的介绍，因此给学习带来了较大的困难。

其次，诸如Java中HashMap的底层实现，在JDK1.8中为了解决过度哈希冲突带来的长链表，会将链表转为红黑树；Linux底层的CFS进程调度算法中，vruntime利用红黑树来进行存储；多路复用技术的Epoll的核心结构也是红黑树+双向链表。

我们不会直接去手写一个可用的红黑树，但是了解红黑树的结构，有助于我们去理解一些底层具体实现。与此同时，红黑树也是对树结构的一种高度综合运用，涉及到多叉树，树平衡调整，节点旋转等等，这些是对数据结构基本功的最佳历练。

其实当面试官提出这个问题的时候，不参照答案，他大概率也无法清晰的给出具体的定义和操作。但是他希望从这个问题出发，看到你对于一个数据结构的理解，考察你知识面的广度和深度。能否给出完整的定义，能否介绍自己对红黑树的认识，能否通过旋转，染色等操作在给定的场景下对一颗红黑树进行调整使其符合定义…这些才是面试官希望从你的答案中得到的信息，问了一圈身边大厂的面试官朋友，跟我这个说法出入不大。

读完这篇文章，你将能够从红黑树的概念模型2-3-4树出发，理解红黑树五大定义背后的逻辑。你也可以深刻认识到红黑节点颜色背后的意义，对于插入删除引发的动态变化有一定的认识，而不再是去硬性的记忆某个场景下的调平操作（诸如：删除某节点，当该节点的叔父节点为红，而叔父节点的左右子节点都为黑的情况下，我们应该…）。你能够掌握节点旋转的具体操作，理解染色的目的。

最后，如果你足够认真，配图中有清晰的插入删除全部步骤，你能够真正的将红黑树变成自己的知识。

先谈平衡树

做开发的朋友一定知道接口这个东西：定义接口，给出实现。一个接口可以有多种不同的实现，但是这些实现都会满足接口中的声明。

例如，我们定义手机是一个可用作通讯的工具，作为它的实现，三星，苹果，华为推出了各式各样的产品。

红黑树的本质其实也是对概念模型：2-3-4树的一种实现，因此我们先来关注2-3-4树。

2-3-4树是阶数为4的B树，B树，全名BalanceTree，平衡树。这种结构主要用来做查找。

关于B树（平衡多路查找树）的定义，网上已经有很多介绍，在此不多赘述。它最重要的特性在于平衡，这使得我们能够在最坏情况下也保持O(LogN)的时间复杂度实现查找（一个不具备平衡性的查找树可能退化成单链表，时间复杂度会到O（N））。

在此需要提醒大家一下，平衡的定义是说从空链接到根节点距离相等，此处一定要用心理解。（也就是说非叶子节点是不会存在空链接的）

由于2-3-4树是一颗阶数为4的B树，所以它会存在以下节点：
- 2节点
- 3节点
- 4节点
2节点中存放着一个key[X]，两个指针，分别指向小于X的子节点和大于X的子节点；3节点中存放在两个key[X,Y],三个指针，分别指向小于X的子节点，介于X~Y之间的子节点和大于Y的子节点；4节点可依此类推。

2-3-4树到红黑树的转化

红黑树是对概念模型2-3-4树的一种实现，由于直接进行不同节点间的转化会造成较大的开销，所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3-4树中不同的节点。

2-3-4树中的2节点对应着红黑树中的黑色节点，而2-3-4树中的非2节点是以红节点+黑节点的方式存在，红节点的意义是与黑色父节点结合，表达着2-3-4树中的3，4节点。

（此处理解成红节点也好，红色链接也好，看个人喜好。很多书中会说是由黑色节点指出的红色链接，链接指向的节点颜色为红。）

我们先看2-3-4树到红黑树的节点转换。2节点直接转化为黑色节点；3节点这里可以有两种表现形式，左倾红节点或者右倾红节点。而4节点被强制要求转化为一个黑父带着左右两个红色儿子。

本文的研究主体是2-3树（原因会在后文给出），并且是2-3树中较为特殊的一种转化–左倾红黑树。顾名思义，左倾红黑树限制了如果在树中出现了红色节点，那么这个节点必须是左儿子。

以下是它的转化过程：

光看单个节点的转化可能还不够明显，我制作了一张红黑树转2-3树的示意图，很清晰地描绘了它们之间的关系。

只要把左倾红黑树中的红色节点顺时针方向旋转45°使其与黑父平行，然后再将它们看作一个整体，你就会发现，这不就是一颗2-3树吗？

至此，我想大家已经明白，红黑树其实就是对概念模型2-3树（或者2-3-4树）的一种实现。

算法导论中给出的是红黑树基于2-3-4树实现，其中4节点要求平衡（即4节点必须用黑色父亲和左右两个红色儿子表示，红色儿子不能出现在同一边）。

算法4中给出的红黑树是基于2-3树实现，而且这种实现的红黑树十分特殊，它要求概念模型中的3节点在红黑树中必须用左倾的红色节点来表示。这种限定能够很大的减少红黑树调整过程中的复杂性，我们将在接下来的内容中体会到这一点。

我将算法导论和算法4中的红黑树反复的看了几遍，最终选择算法4中的红黑树做演示主体。
- 首先，算法4中的红黑树基于2-3树概念模型，不用考虑2-3-4树中复杂的4节点分裂；
- 第二，算法4中的红黑树是左倾红黑树，进一步降低了调平的难度；
- 第三，算法导论中对于红黑树删除场景的阐述并不够具体，许多关键环节都用“经过一定的旋转和变色处理”来带过，不利于新手的学习。（我花了很长时间还原具体过程）。
  
  考虑到部分读者有充足的精力研究以2-3-4树为概念模型的红黑树，在介绍2-3树的同时也会带上2-3-4树的基础知识，帮助学有余力的读者去理解算法导论中的红黑树。（所以如果没有必要，只看2-3树的部分就行）。
我们在了解红黑树的插入删除操作之前，需要先了解2-3树的插入删除操作，这样才能理解红黑树中染色和旋转背后的意义。

让我们来看一下对于2-3树的插入。我们的插入操作需要遵循一个原则：先将这个元素尝试性地放在已经存在的节点中，如果要存放的节点是2节点，那么插入后会变成3节点，如果要存放的节点是3节点，那么插入后会变成4节点（临时）。然后，我们对可能生成的临时4节点进行分裂处理，使得临时4节点消失。

如果需要在2-3-4树中向4节点内插入元素，那么会引发如下图所示的分裂过程

事实上，这正对应了红黑树在插入的时候一定会把待插入节点涂成红色，因为红色节点的意义是与父节点进行关联，形成概念模型2-3树中的3节点或者临时4节点。

而红黑树之所以需要在插入后进行调整，正是因为可能存在着概念模型中的临时4节点（反应在红黑树中是双红的情况）。

试想在2-3树中如果待插入节点是个2节点，那么反应在红黑树中，不正好对应着黑色父节点吗，在黑色父节点下面增加一个红色儿子，确实不会违背红黑树的任何规则，这也对应着我们向2-3树中的2节点插入一个元素，只需要简单的把2节点变成3节点。

接下来让我们来看一下对于2-3树的删除。对于2-3树的删除我们主要要考虑待删除元素在2节点这种情况，因为如果待删除元素在3节点，那么可以直接将这个元素删除，而不会破坏2-3树的任何性质（删除这个元素不会引起高度的变化）。

当待删除元素在2节点的时候，由于删除这个元素会导致2节点失去自己唯一的元素，引发2节点自身的删除，会使得树中某条路径的高度发生变化，树变得不平衡。

因此我们有两种方案去解决这个问题：
- 第一种方案，先删除这个2节点，然后对树进行平衡调整。
- 第二种方案，我们想办法让这个被删除的元素不可能出现在2节点中。
本文选择第二种方案，我们在搜索到这个节点的路径中，不断地判断当前节点是否为2节点，如果是，就从它的兄弟节点或者它的父节点借一个元素，使得当前节点由2节点成为一个3节点或者一个临时4节点（视具体情况而定，在后面的红黑树部分会详细介绍）。

这种操作会产生一种结果：除非当前节点是根节点，否则当前节点的父节点一定是一个非2节点（因为搜索的路径是自上而下，父节点已经进行过了这种操作，所以不可能是2节点），那么我们可以保证到达叶子节点的时候，也能顺利的从父节点或者兄弟节点处借到元素，使得自己成为非2节点。从而能够直接删除某个元素（现在这个元素不在2节点中了）。

再看红黑树

来看它的五条定义：

1.节点颜色有红色和黑色

【2-3树到红黑树的转化已经解释过】

2.根节点必为黑色

【2-3树中如果根节点为2节点，那么它本来就对应红黑树中黑节点；如果根节点为3节点，也可以用黑色节点表示较大的那个元素，然后较小的元素作为左倾红节点存在于红黑树中】

3.所有叶子节点都是黑色

【此处提到的叶子其实是空链接，因篇幅问题不便全部画出】

####4.任意节点到叶子节点经过的黑色节点数目相同

【红黑树中的红节点是和黑色父节点绑定的，在2-3树中本来就是同一层的，只有黑色节点才会在2-3树中真正贡献高度，由于2-3树的任一节点到空链接距离相同，因此反应在红黑树中就是黑色完美平衡】

5.不会有连续的红色节点

【2-3树中本来就规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点】

相信在你的视角中，红黑树已经不再是这五条僵硬的定义了，它背后正浮现着一颗2-3树概念模型。虽然你已经有了这样的认识，但是红黑树作为真正的实现模型，我们还是要回到这个实现本身来探究它的一系列操作。在开始前，我准备了两个基础知识，希望能帮助到你。

1.作为二叉查找树

二叉查找树的节点有一个元素X和两个指针域，左指针指向小于X的元素，右指针指向大于X的元素。

假设我们的插入序列是1~10，那么这颗树会演变成只有右链接的形式，树高会增加到10层，这个时候已经不具备O(LogN)的查找时间复杂度，因为这颗树退化成了链表。

因此对二叉树进行平衡调整是很重要的一个环节，无论是AVL还是红黑树，它们本质上都是希望尽可能保证这颗二叉查找树中的元素尽量均衡的分布在树的两侧。

当我们向一颗二叉查找树中插入一个元素Y的时候，我们会一直与树中的节点进行大小比较，如果Y小于当前元素，就往左走，如果Y大于当前元素，就往右走，直到达到叶子节点，这个时候我们可以把Y插入这颗二叉查找树了。

由于这次的插入动作，整棵树可能会发生一些不平衡，因此我们需要在插入后进行一次平衡调整，使得整棵树恢复到平衡的状态（具体如何调整，要看树是AVL还是红黑树亦或是其他的平衡树）。

二叉查找树的删除是一个很有意思的问题，不同于插入的是，待删除的元素并不能保证一定出现在树中的叶子节点。这将带来一个棘手的情景，即我们需要从树的中间部分取走一个元素，而且在取走后还需要经过调整来使得整颗树满足平衡的性质。从树的中间部分直接取走一个节点的场景实在是太多，也牵扯到了太多相关的节点，这种操作很难实现。

好在有人提出了一个观点，我们对查找树中一个节点的删除，其实可以不必真的改动这个节点的位置。由于查找树的特殊性质，将某个元素节点删除后，它有两个最佳替代者，分别是有序序列中的前驱元素和后继元素。

我们还是以一个包含元素1~10的二叉查找树为例，如果我们希望删除5所在的节点，那么让4或者6替代它的位置都是可行的。作为前驱元素的4，会存放在5所在节点的左子树的最右侧；作为后继元素的6，会存放在5所在节点的右子树的最左侧。

关于这个结论，大家只需稍加思索便可以明白。

现在我们又让问题简化了，也就是说，删除某个节点的时候，我们先找到它的前驱元素或者后继元素（随便选一个），将它的前驱元素直接填到待删除的节点，然后再把它的前驱元素或者后继元素删除。

这个时候问题就转化成了在二叉查找树中删除一个没有左子树的节点（或者是一个没有右子树的节点），我们只需要将这个节点删除再进行对应的平衡调整即可（虽然还是需要调平，但是比直接在树中层删除一个同时具备左右儿子的节点要容易很多）。

注意，此处并没有强调是针对红黑树的操作，因为红黑树和AVL都是二叉查找树，它们都适用这个方法。

介绍一下树的旋转

为了调平一颗二叉树，使得其左右节点数目分布均匀，通常会选择旋转的手段。你可以把一颗二叉树某节点的左右子树想象成天平上待称量的物品，如果哪边重了，我们就从重的那边拿出一部分，加到轻的那边，以此保持相对的平均。

在二叉树中这种调整的操作就是旋转，下面给出了两个示例，希望大家能够仔细探究，旋转是二叉树调平的精髓。

介绍一下树的旋转

理解了这些之后，再去看红黑树的插入删除，就能够理解旋转和染色背后的意义了。
我们选择算法4中的左倾红黑树作演示：首先看插入

如图所示，对于左倾红黑树的插入一共有三种可能的情况。
- 第一种，待插入元素比黑父大，插在了黑父的右边，而黑父左边是红色儿子。这种情况会导致在红黑树中出现右倾红节点。
  
  注意，这种情况对应着2-3树中出现了临时4节点，我们在2-3树中的处理是将这个临时4节点分裂，左右元素各自形成一个2节点，中间元素上升到上层跟父节点结合。所以，我们在红黑树中的动作是，将原本红色的左右儿子染黑（左右分裂），将黑父染红（等待上升结合）。
- 第二种情况，待插入元素比红父小，且红父自身就是左倾。听起来有点绕，看图就会明白，其实就是说红父和待插入元素同时靠在了左边，形成了连续的红节点。
  
  这种情况我们需要用两步来调整。由于我们插入的是红色节点，其实不会破坏黑色完美平衡，所以要注意的是在旋转和染色的过程种继续保持这种完美黑色平衡。
  
  首先对红父的父亲进行一次右旋，这次右旋不会破坏黑色平衡，但是也没有解决连续红色的问题。
  
  接下来将12所在节点与15所在节点交换颜色，这样的目的是为了消除连续红色，并且这个操作依旧维持了黑色平衡。现在我们已经得到了情况1的场景，直接按情况1处理即可。
- 第三种情况，待插入元素比红父大，且红父自身就是左倾。
  
  也就是说插入的这个节点形成了一个右倾的红色节点，对右倾的处理很简单，将红父进行一次左旋，就能使得右倾红节点变为左倾，现在出现了连续的左倾红节点，直接按情况2处理即可。
在插入时，可以体会到左倾红黑树对于左倾的限制带来的好处，因为在原树符合红黑树定义的情况下，如果父亲是红的，那么它一定左倾，同时也不用考虑可能存在的右倾兄弟（如果有，那说明原树不满足红黑树定义）。

这种限制消除了很多需要考虑的场景，让插入变得更加简单。

左倾红黑树的删除

左倾红黑树的删除需要借鉴上文中提到的二叉查找树通用的删除策略，当我们要删除某个节点的时候选择它的前驱节点或者后继节点元素来替代它，转而删除它的前驱/后继节点。

在这个例子中，我选择用后继节点来替代被删除节点。

假设我们需要删除的节点它的右子树如图所示，那么对该节点的删除实际上转为了对2的删除。

我们从当前的根节点出发，利于2-3树中预合并的策略逐层对红黑树进行调整。具体的做法是，每次都保证当前的节点是2-3树中的非2节点，如果当前节点已经是非2节点，那么直接跳过；如果当前节点是2节点，那么根据兄弟节点的状况来进行调整：
- 如果兄弟是2节点，那么从父节点借一个元素给当前节点，然后与兄弟节点一起形成一个临时4节点。
- 如果兄弟是非2节点，那么兄弟上升一个元素到父节点，同时父节点下降一个元素到当前节点，使得当前节点成为一个3节点。
这样的策略能够保证最后走到待删除节点的时候，它一定是一个非2节点，我们可以直接将其元素删除。

接下来要考虑的是修复工作，由于红黑树定义的限制，我们在调整的过程中出现了一些本不该存在的红色右倾节点（因为生成了概念模型中的临时4节点），于是我们顺着搜索的方向向上回溯，如果遇到当前节点具备右倾的红色儿子，那么对当前节点进行一次左旋，这时原本的右儿子会来到当前节点的位置，然后将右儿子与当前节点交换颜色，我们就将右倾红节点修复成了左倾红节点，同时我们并没有破坏黑色节点的平衡。

右倾转左倾是一个很基本的操作，我们以35，44为例，你既可以将35作为黑节点，44作为右倾红色儿子；也可以将44作为黑节点，35作为左倾红儿子。事实上我们对于右倾的修复就是换了一种树形而已。一路回溯到当前根节点，直至路径中不再包含任何的红色右倾节点，至此修复工作全部完成。

总结

这篇文章的目的旨在从概念模型2-3树出发介绍一颗红黑树的前世今生。希望大家能够跳出枯燥的五条定义，更加本质地认识红黑树中的各种操作来源。

虽然本文只是介绍了相对简单的左倾红黑树，但是如果能够将左倾红黑树认识的很清楚，那么普通红黑树也只是多了一些情况而已。

对于还有精力阅读算法导论的读者，我给出一点自己的经验：
- 插入阶段与左倾红黑树比较相似
- 配图中的部分节点标识不太清楚，要反复对照原文阅读
- 删除阶段，算法导论中将删除黑节点X带来的黑色平衡破坏解释为，给X的子节点添上额外的一层黑色，让X的子节点变为【双重黑】或者【既黑又红】的。
  
  我其实不太接受这种解释，经过考虑，我认为其实这个表达可以更直接一点：既然删除了某个黑色节点，那么必然会破坏以这个黑色节点为路径上的黑色平衡，表现为路径中缺少一个黑。
  
  如果你仔细研究算法导论中的四个删除场景，会发现它们在做的事情其实都是从兄弟节点的路径想办法移动一个黑色节点过来。
  
  因此，如果实在无法理解【双重黑】，【既黑又红】，那么直接按照“某条路径欠黑，所以要想办法补充一个黑色节点”这个思路来思考吧！
- 还是删除阶段，四个删除场景该如何记忆？我们假设删除的是某个左倾节点，其实决定场景变化的就是三个因素：这个节点的兄弟颜色；兄弟的左右儿子的颜色；这个节点的父节点的颜色。这样子粗略估计有2x2x2x2共16种情况。实际上会少很多，我们从兄弟的颜色入手。请注意如果兄弟是红色，那么当前节点的父亲和兄弟的儿子其实都是黑色。而当兄弟是黑色的时候，我们只需要满足兄弟的右儿子是红色，就能通过一次调整来实现平衡（具体请参照算法导论）。
  
  另外提醒注意的是，一定要想好记忆的顺序。算法导论中的删除调平4种情况中，只有情况4是绝对终态，也就是说到达了这种状态后只需要一次调整绝对能达到平衡。所以我们的出发点一定是从这种状态开始，对于另外几种情况，我们要想的不是怎么去达到最终平衡，而是怎么能让它一步一步转为情况4。这样子你的思路就会清晰很多，记忆的压力也会减小。如果细心的话，你可以回想一下本文是按照怎样的顺序介绍左倾红黑树的插入的，为什么是这样的顺序？
- 一个数据结构可视化网站，它的红黑树是基于2-3-4树的，跟算法导论中基本一样（除了删除时候对前驱/后继节点的选择），可以用它当做检验。https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
写在最后

最后，如果你被问到红黑树，也许你可以试着反问面试官一个问题：“您应该知道红黑树的五条定义，如果我构造一颗只有黑色节点的红黑树，这样子可行吗？因为这样子没有破坏任何一条红黑树的规则。”

如果他回答可行。

继续问：“那么请问红黑树中要红节点干什么呢？红节点的真实意义是什么呢？”

你们的故事就开始了，而我和你的算法故事也才刚开始。

絮叨

敖丙把自己的面试文章整理成了一本电子书，共 1630页！

干货满满，字字精髓。目录如下，还有我复习时总结的面试题以及简历模板，现在免费送给大家。

链接:https://pan.baidu.com/s/1ZQEKJBgtYle3v-1LimcSwg 密码:wjk6

我是敖丙，你知道的越多，你不知道的越多，感谢各位人才的：点赞、收藏和评论，我们下期见！

文章持续更新，可以微信搜一搜「 三太子敖丙 」第一时间阅读，回复【资料】有我准备的一线大厂面试资料和简历模板，本文 GitHub https://github.com/JavaFamily 已经收录，有大厂面试完整考点，欢迎Star。
收起
展开全文
红黑树生成删除
2019-07-04 17:36:38

红黑树在线生成的一个工具，从网上找的，我这样应该得不到分。大哭https://www.cnblogs.com/bbvi/p/5576201.html 删除可能存在问题，替换节点的兄弟节点为黑色节点时有问题，其他部分是没有问题的，凑合着看看

收起

红黑树
【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树
千次阅读 多人点赞 2022-01-17 17:04:24
狂肝半个月的学习笔记，最通俗易懂的红黑树讲解。带你快速掌握红黑树~
目录

一、红黑树简介

二、为什么需要红黑树？

三、红黑树的特性

四、红黑树的效率

4.1 红黑树效率

4.2 红黑树和AVL树的比较

五、红黑树的等价变换

六、红黑树的操作

6.1 旋转操作

6.2 插入操作

6.2.1 插入操作的所有情况

6.2.2 LL和RR插入情况

6.2.3 LR和RL插入情况

6.2.4 上溢的LL插入情况

6.2.5 上溢的RR插入情况

6.2.6 上溢的LR插入情况

6.2.7 上溢的RL插入情况

6.2.8 插入情况总结

6.3 删除操作

6.3.1 删除操作的所有情况

6.3.2 删除拥有1个红色子节点的黑色节点

6.3.3 删除黑色叶子节点——删除节点为根节点

6.3.4 删除黑色叶子节点——删除节点的兄弟节点为黑色

6.3.5 删除黑色叶子节点——删除节点的兄弟节点为红色

七、红黑树的平衡

八、红黑树的平均时间复杂度

九、AVL树 vs 红黑树

9.1 AVL树

9.2 红黑树

9.3 如何选择

9.4 案例对比

9.4.1 二叉搜索树

9.4.2 AVL树

9.4.3 红黑树

大家应该都学过平衡二叉树(AVLTree)，了解到AVL树的性质，其实平衡二叉树最大的作用就是查找,AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。AVL树的效率就是高在这个地方。如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏，它就不再是一棵二叉树；为了让它重新维持在一个平衡状态，就需要对其进行旋转处理, 那么创建一颗平衡二叉树的成本其实不小. 这个时候就有人开始思考，并且提出了红黑树的理论，红黑树在业界应用很广泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树结构实现的。那么红黑树到底比AVL树好在哪里？

一、红黑树简介

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明，在当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率，它可在 O(logN) 时间内完成查找、增加、删除等操作。

二、为什么需要红黑树？

对于二叉搜索树，如果插入的数据是随机的，那么它就是接近平衡的二叉树，平衡的二叉树，它的操作效率（查询，插入，删除）效率较高，时间复杂度是O（logN）。但是可能会出现一种极端的情况，那就是插入的数据是有序的（递增或者递减），那么所有的节点都会在根节点的右侧或左侧，此时，二叉搜索树就变为了一个链表，它的操作效率就降低了，时间复杂度为O(N)，所以可以认为二叉搜索树的时间复杂度介于O（logN）和O(N)之间，视情况而定。那么为了应对这种极端情况，红黑树就出现了，它是具备了某些特性的二叉搜索树，能解决非平衡树问题，红黑树是一种接近平衡的二叉树（说它是接近平衡因为它并没有像AVL树的平衡因子的概念，它只是靠着满足红黑节点的5条性质来维持一种接近平衡的结构，进而提升整体的性能，并没有严格的卡定某个平衡因子来维持绝对平衡）。

三、红黑树的特性

在讲解红黑树性质之前，先简单了解一下几个概念：
- parent：父节点
- sibling：兄弟节点
- uncle：叔父节点（ parent 的兄弟节点）
- grand：祖父节点（ parent 的父节点）
首先，红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）。它同时满足以下特性：
1. 节点是红色或黑色
2. 根是黑色
3. 叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），下图中的那些null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点
4. 红色节点的子节点都是黑色
  红色节点的父节点都是黑色
  从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
5. 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点
根据上面的性质，我们来判断一下下面这课树是不是红黑树

上面这棵树首先很容易就能知道是满足性质1-4条的，关键在于第5条性质，可能乍一看好像也是符合第5条的，但实际就会陷入一个误区，直接将图上的最后一层的节点看作叶子节点，这样看的话每一条从根节点到叶子结点的路径确实都经过了3个黑节点。

但实际上，在红黑树中真正被定义为叶子结点的，是那些空节点，如下图。

这样一来，路径1有4个黑色节点（算上空节点），路径2只有3个黑色节点，这样性质5就不满足了，所以这棵树并不是一个红黑树节点。

注：下面的讲解图中将省略红黑树的null节点，请自行脑补

四、红黑树的效率

4.1 红黑树效率

红黑树的查找，插入和删除操作，时间复杂度都是O(logN)。

查找操作时，它和普通的相对平衡的二叉搜索树的效率相同，都是通过相同的方式来查找的，没有用到红黑树特有的特性。

但如果插入的时候是有序数据，那么红黑树的查询效率就比二叉搜索树要高了，因为此时二叉搜索树不是平衡树，它的时间复杂度O(N)。

插入和删除操作时，由于红黑树的每次操作平均要旋转一次和变换颜色，所以它比普通的二叉搜索树效率要低一点，不过时间复杂度仍然是O(logN)。总之，红黑树的优点就是对有序数据的查询操作不会慢到O(logN)的时间复杂度。

4.2 红黑树和AVL树的比较
1. AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
2. 红黑树的插入删除比AVL树更便于控制操作
3. 红黑树整体性能略优于AVL树（红黑树旋转情况少于AVL树）
五、红黑树的等价变换

上面这颗红黑树，我们来将所有的红色节点上移到和他们的父节点同一高度上，就会形成如下结构

这个结构很明显，就是一棵四阶B树（一个节点最多放三个数据），如果画成如下的样子大家应该就能看的更清晰了。

由上面的等价变换我们就可以得到如下结论：
1. 红黑树和 4阶B树（2-3-4树）具有等价性
2. 黑色节点与它的红色子节点融合在一起，形成1个B树节点
3. 红黑树的黑色节点个数与 4阶B树的节点总个数相等
4. 在所有的B树节点中，永远是黑色节点是父节点，红色节点是子节点。黑色节点在中间，红色节点在两边。
我们可以利用四阶B树与红黑树等价的性质，以红黑树转换成B树之后的节点情况来进行一个分类

六、红黑树的操作

红黑树的基本操作和其他树形结构一样，一般都包括查找、插入、删除等操作。前面说到，红黑树是一种自平衡的二叉查找树，既然是二叉查找树的一种，那么查找过程和二叉查找树一样，比较简单，这里不再赘述。相对于查找操作，红黑树的插入和删除操作就要复杂的多。尤其是删除操作，要处理的情况比较多，下面就来分情况讲解。

6.1 旋转操作

在分析插入和删除操作前，先说明一下旋转操作，这个操作在后续操作中都会用得到。旋转操作分为左旋和右旋，左旋是将某个节点旋转为其右孩子的左孩子，而右旋是节点旋转为其左孩子的右孩子。这话听起来有点绕，所以还是请看下图：

上图包含了左旋和右旋的示意图，这里以右旋为例进行说明，右旋节点 M 的步骤如下：
1. 将节点 M 的左孩子引用指向节点 E 的右孩子
2. 将节点 E 的右孩子引用指向节点 M，完成旋转
旋转操作本身并不复杂，上面分析了右旋操作，左旋操作与此类似，只是右旋转的逆操作。

6.2 插入操作

红黑树的插入过程和二叉查找树插入过程基本类似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。

性质1规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色还是黑色呢？答案是红色，原因也不难理解。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦（参考红黑树的删除操作，就知道为啥多一个或少一个黑色节点时，调整起来这么麻烦了）。如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前的简单多了。所以插入的时候将节点设置为红色，可以保证满足性质 1、2、3、5 ，只有性质4不一定满足，需要进行相关调整。如果是添加根节点，则将节点设定为黑色。

6.2.1 插入操作的所有情况

我们在分析红黑树各种插入情况的时候，将其等价转换为B树，这样我们能够更直观的进行分类，首先确定几条性质：
- B树中，新元素必定是添加到叶子节点中（最底层的节点）
- 4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3
在上一章节红黑树的等价变换中，我们讲到了红黑树转换成B树总共有四种情况，也就是上图中叶子节点这四种情况，那么在我们进行插入操作的时候，会将节点插入到所有的叶子节点中，总共就会有12种情况，其中四种情况满足红黑树的性质，8种情况不满足红黑树性质。

6.2.1.1 满足红黑树性质4

有 4 种情况满足红黑树的性质 4 ：parent 为黑色节点。这四种情况不需要做任何额外的处理。

6.2.1.2 不满足红黑树性质4

有 8 种情况不满足红黑树的性质 4 ：parent 为红色节点（ Double Red ），其中左面4种属于B树节点上溢的情况（一个4阶B树节点中最多存放三个数，这四种情况本来已经有3个了，又插入了1个，变成了4个，超出了4阶B树节点的容量范围，这种情况称为上溢）。这八种情况需要进行额外的处理。

6.2.2 LL和RR插入情况

如上图，插入52和60的位置分别是RR情况和LL情况。

RR情况：父节点为祖父节点的右节点，插入节点为父节点的右节点

LL情况：父节点为祖父节点的左节点，插入节点为父节点的左节点

这两种情况很明显，插入节点为红色，父节点也为红色，父节点的子节点为红色显然违背了红黑树的性质四，我们需要对这种情况进行修复，使其重新满足红黑树性质。

判定条件：uncle 不是红色节点。

这里的两种情况，他们的插入节点都是没有叔父节点的，所以叔父节点也不可能是红色。

案例修复：

我们在红黑树等价转换那一章节也讲过了，红黑树等价转换成B树之后，B树节点的中间节点（父节点）都是黑色，两边的节点（子节点）都是红色。但是上面两种情况插入后，插入位置的B树节点并不满足这个条件，所以我们对其进行修复，使其满足B树节点的条件之后，也就重新恢复了红黑树性质。

B树节点中的中间节点大小介于两个子节点之间。以上图RR情况为例，插入节点52的原父节点应该放在B树节点中间的位置，应当将其染成黑色。插入节点52的原祖父节点46，应当将其转换为插入节点原父节点的子节点，所以将其染成红色。LL情况同理

完成染色之后，需要对原祖父节点进行单旋操作，来进行父节点，子节点的重新分配。以上图为例：
- RR情况应该原祖父节点46左旋，将插入节点的原父节点50旋转到中间的位置。
- LL情况应当原祖父节点76右旋，将插入节点的原父节点72旋转到中间的位置。
修复之后的结果如下图：

修复步骤总结：
1. parent 染成黑色，grand 染成红色
2. grand 进行单旋操作
  LL：右旋转
  RR：左旋转
6.2.3 LR和RL插入情况

如上图，插入48和74的位置分别是RL情况和LR情况。

RL情况：父节点为祖父节点的右节点，插入节点为父节点的左节点

LR情况：父节点为祖父节点的左节点，插入节点为父节点的右节点

这两种情况和上面的两种情况一样，插入节点为红色，父节点也为红色，父节点的子节点为红色显然违背了红黑树的性质四，我们需要对这种情况进行修复，使其重新满足红黑树性质。

判定条件：uncle 不是红色节点。

这两种情况的插入节点也是没有叔父节点的。

案例修复：

B树节点中的中间节点大小介于两个子节点之间。以上图RL情况为例，插入节点48大小介于原父节点和原祖父节点之间，它应该是B树节点中的中间节点，所以将插入节点48染成黑色，将原祖父节点46染成红色来作为插入节点的子节点。LR情况同理

完成染色之后，需要进行双旋操作，来进行父节点，子节点的重新分配。以上图为例：
- RL情况应该原父节点50右旋，将插入节点48上移到原父节点50的高度，然后将插入节点的原祖父节点46进行左旋，将插入节点48移动到中间位置，成为中间节点。
- LR情况应该原父节点72左旋，将插入节点74上移到原父节点72的高度，然后将插入节点的原祖父节点76进行右旋，将插入节点74移动到中间位置，成为中间节点。
修复之后的结果如下图：

修复步骤总结：
1. 插入节点染成黑色，grand 染成红色
2. 进行双旋操作
  LR：parent 左旋转， grand 右旋转
  RL：parent 右旋转， grand 左旋转
6.2.4 上溢的LL插入情况

如上图，插入10的位置是上溢的LL情况。

上溢LL情况：父节点为祖父节点的左节点，插入节点为父节点的左节点。并且构成的新的B树节点已经超过了B树节点容量大小范围。

这种情况和之前非上溢的四种情况一样，插入节点为红色，父节点也为红色，父节点的子节点为红色显然违背了红黑树的性质四，我们需要对这种情况进行修复，使其重新满足红黑树性质。

判定条件：uncle 是红色节点。满足这个条件的就都是上溢的情况，上溢的修复只需要染色，不需要旋转。

案例修复：

像这种上溢的情况，就需要从溢出的B树节点中选出一个节点进行向上合并，选择B树节点中中间的树去进行向上合并，这里中间的两个节点就是原父节点17和原祖父节点25，选这两个哪一个向上合并都是对的，但是我们最好选择以后方便操作的，很显然，应该选择原祖父节点25来进行向上合并，因为向上合并就是和最上层的38和55来组合成新的B树节点，向上合并的节点肯定是一个子节点，需要与上层相连，而原祖父节点25本身就已经和上层连接了，相对更加方便后续的操作。原祖父节点向上合并后，将其染成红色。

原祖父节点25向上合并后，它原来左右两边的节点需要分裂成两个子树，也就是原父节点17和插入节点10形成一个子树，原叔父节点33形成一个子树。这两个分裂形成的树都是以后25的子树。左边的子树由原父节点作为中间节点，染成黑色，右边的子树由原叔父节点作为中间节点，染成黑色。

修复之后的结果如下图：

修复步骤总结：
1. parent、uncle 染成黑色
2. grand 向上合并
  将向上合并的grand染成红色，相对上一层，就当做是新添加的节点，再次来一遍插入情况的判断，进行处理。
grand 向上合并时，可能继续发生上溢。这种情况就继续递归调用修复方法就可以了。若上溢持续到根节点，只需将根节点染成黑色即可（这个意思就是说断向上上溢，一直上溢到了B树的根节点位置了，只需要将向上合并的节点变成黑色作为红黑树的根节点即可。因为从B树根节点选择出来上溢的节点，肯定就是作为整个红黑树的根节点了）。

6.2.5 上溢的RR插入情况

如上图，插入36的位置是上溢的RR情况。

上溢RR情况：父节点为祖父节点的右节点，插入节点为父节点的右节点。并且构成的新的B树节点已经超过了B树节点容量大小范围。

判定条件：uncle 是红色节点

案例修复：

上溢RR情况的修复，和上溢LL情况基本一致，只是修复的位置不同，这里中间的两个节点就是原父节点33和原祖父节点25，选择原祖父节点25来进行向上合并，原祖父节点向上合并后，将其染成红色。

原祖父节点25向上合并后，它原来左右两边的节点需要分裂成两个子树，也就是原父节点33和插入节点36形成一个子树，原叔父节点17形成一个子树。这两个分裂形成的树都是以后25的子树。左边的子树由原叔父节点作为中间节点，染成黑色，右边的子树由原父节点作为中间节点，染成黑色。

修复之后的结果如下图：

修复步骤总结：
1. parent、uncle 染成黑色
2. grand 向上合并
  染成红色（其实染成红色就已经是完成了向上合并，因为祖父节点和祖父节点的父节点的连接指向并没有变），当做是新添加的节点进行处理
6.2.6 上溢的LR插入情况

如上图，插入20的位置是上溢的LR情况。

上溢LR情况：父节点为祖父节点的左节点，插入节点为父节点的右节点。并且构成的新的B树节点已经超过了B树节点容量大小范围。

判定条件：uncle 是红色节点

案例修复：

上溢LR情况的修复，和其他上溢情况基本一致，只是修复的位置不同，这里中间的两个节点就是原父节点17和原祖父节点25，选择原祖父节点25来进行向上合并，原祖父节点向上合并后，将其染成红色。

原祖父节点25向上合并后，它原来左右两边的节点需要分裂成两个子树，也就是原父节点17和插入节点20形成一个子树，原叔父节点33形成一个子树。这两个分裂形成的树都是以后25的子树。左边的子树由原父节点作为中间节点，染成黑色，右边的子树由原叔父节点作为中间节点，染成黑色。

修复之后的结果如下图：

修复步骤总结：
1. parent、uncle 染成黑色
2. grand 向上合并
  染成红色，当做是新添加的节点进行处理
6.2.7 上溢的RL插入情况

如上图，插入30的位置是上溢的RL情况。

上溢RL情况：父节点为祖父节点的右节点，插入节点为父节点的左节点。并且构成的新的B树节点已经超过了B树节点容量大小范围。

判定条件：uncle 是红色节点

案例修复：

上溢RL情况的修复，和其他上溢情况基本一致，只是修复的位置不同，这里中间的两个节点就是原父节点33和原祖父节点25，选择原祖父节点25来进行向上合并，原祖父节点向上合并后，将其染成红色。

原祖父节点25向上合并后，它原来左右两边的节点需要分裂成两个子树，也就是原父节点33和插入节点30形成一个子树，原叔父节点17形成一个子树。这两个分裂形成的树都是以后25的子树。左边的子树由原叔父节点作为中间节点，染成黑色，右边的子树由原父节点作为中间节点，染成黑色。

修复之后的结果如下图：

修复步骤总结：
1. parent、uncle 染成黑色
2. grand 向上合并
  染成黑色，当做是新添加的节点进行处理
6.2.8 插入情况总结

插入一共有12种情况：
1. 插入节点的父节点是黑色的情况有4种
  这种情况仍然会维持红黑树的性质，则不需要进行额外处理。
2. 插入节点的父节点是红色的情况有8种
  这种情况不满足红黑树的性质4，需要进行额外的修复处理。
  这8种情况中：
  叔父节点不是红色的情况有4种
  这些情况都是非上溢，需要通过重新染色和旋转来进行修复
  叔父节点是红色的情况有4种
  这些情况都是上溢的，只需要通过祖父节点上溢合并和染色即可完成修复
6.3 删除操作

相较于插入操作，红黑树的删除操作则要更为复杂一些。B树中，最后真正被删除的元素都在叶子节点中。所以在红黑树中，被删除的节点一定也在最后一层。

6.3.1 删除操作的所有情况

上面我们说删除节点一定都在最后一层，最后一层有红色节点和黑色节点，我们就以删除节点的颜色来区分删除操作的所有情况。

6.3.1.1 删除红色节点

如果删除的节点是红色直接删除，不用作任何调整。因为删除最后一层的红色节点，并没有影响红黑树的任何性质。

6.3.1.2 删除黑色节点

有3种情况：
1. 拥有 2 个红色子节点的黑色节点
  不可能被直接删除，因为会找它的子节点替代删除，因此不用考虑这种情况
2. 拥有 1 个红色子节点的黑色节点
3. 黑色叶子节点
6.3.2 删除拥有1个红色子节点的黑色节点

删除拥有1个红色子节点的黑色节点的情况，是需要我们做相关的处理的。这里删除的就是节点46和76，他们只有一个红色子节点。

对于一个二叉树来说，删除一个度为1的节点（度指的是一个节点的子节点个数），将其删除后需要用它唯一的子节点来进行替换。而红黑树的这种情况的判定条件，就是判定要替代删除节点的子节点是不是红色

判定条件：用以替代的子节点是红色节点

案例修复：

删除黑色节点46和76

第一步：

将46与父节点的连接断开

第二步：

46唯一的红色子节点50作为代替46的节点，将其与46的父节点进行连接

第三步：

断开46与50的连接，将46删除

删除节点76的过程与删除节点46相同

第一步：

第二步：

第三步：

但是现在我们发现，80是红色节点，它的子节点72还是红色节点，这样明显不符合红黑树的性质，还需要进一步修复。

将替代的子节点染成黑色即可保持红黑树性质，修复完成

修复步骤总结：
1. 用删除节点的唯一子节点对其进行替代
2. 将替代节点染成黑色
6.3.3 删除黑色叶子节点——删除节点为根节点

一棵红黑树只有一个黑色根节点（也就是唯一的一个叶子节点，整个红黑树只有这一个黑色节点），可直接删除该节点，无需做其他操作。

6.3.4 删除黑色叶子节点——删除节点的兄弟节点为黑色

讲这种删除情况前先举一个例子

上面这个我们要删除节点88，该节点为黑色叶子节点，它的兄弟节点是黑色76。从B树的角度来看，如果删除88，因为四阶B树的节点中最少存有1个元素，如果不足，则会造成下溢。也就是需要从88的兄弟节点中借一个子节点出来。这就是这一节我们讨论的删除情况的核心修复思想。

6.3.4.1 兄弟节点至少有1个红色子节点

下面三个图分别对应着兄弟节点至少有一个红色子节点的三种情况。删除节点为88，为黑色叶子节点，它的兄弟节点是76，为黑色。兄弟节点76都至少有一个红色子节点，三种情况分别为76拥有一个红色右子节点，76拥有一个红色左子节点，76拥有两个红色子节点。因为兄弟节点有红色子节点，所以可以借出一个节点来进行修复。

这三种情况，黑色叶子节点被删除后，会导致B树节点下溢（比如删除88），就可以从兄弟节点中借出一个红色子节点来进行修复。

判定条件：兄弟节点至少有 1 个红色子节点

案例修复：

1、兄弟节点有一个右子节点：

先将88节点删除

删掉之后，从B树的角度来看就出现了下溢，这个时候就需要父节点下来，在兄弟节点的子结点中找一个，将他升上去代替。具体的实现就是要对节点进行旋转。

我们可以看出，80、76、78组成的树是一个LR的情况，先对76进行左旋转（可以将76看作父节点），这样78就上去了，再对80进行右旋转（可以将80看成祖父节点），80就下去了。

旋转完了之后，如上图。将旋转完之后的中心节点（就是78、76、80组成的树的最中心的节点，这里就是78）进行重新染色，继承删除节点的父节点80的颜色。最后再将78、76、80组成的树的左右两个节点染成黑色即可完成修复。

2、兄弟节点有一个左子节点：

先将88节点删除

删掉之后，从B树的角度来看就出现了下溢，这个时候就需要父节点下来，在兄弟节点的子结点中找一个，将他升上去代替。具体的实现就是要对节点进行旋转。

我们可以看出，80、76、78组成的树是一个LL的情况，直接对80进行右旋（将80看成是祖父节点）。

旋转完了之后，如上图。将旋转完之后的中心节点（就是78、72、80组成的树的最中心的节点，这里就是76）进行重新染色，继承删除节点的父节点80的颜色。最后再将78、72、80组成的树的左右两个节点染成黑色即可完成修复。

3、兄弟节点有两个左右子节点：

先将88节点删除

删除之后，其实可以有两种旋转可以进行修复，既可以使用LL方式进行旋转，也可以使用LR方式进行旋转。但是因为LL方式只需要旋转一次，我们就选用LL方式。

直接对80进行右旋

旋转完了之后，如上图。将旋转完之后的中心节点（就是78、72、76、80组成的树的最中心的节点，这里就是76）进行重新染色，继承删除节点的父节点80的颜色。最后再将78、72、76、80组成的树的左右两个节点染成黑色即可完成修复。

修复步骤总结：
1. 进行旋转操作
2. 旋转之后的中心节点继承父节点（删除节点的父节点）的颜色
3. 旋转之后的左右节点染为黑色
6.3.4.2 兄弟节点没有红色子节点

当删除节点的兄弟节点没有红色节点可以借出的情况下，就需要父节点来向下合并进行修复，父节点向下和兄弟节点合并成新的B树节点来解决下溢。

判定条件：兄弟节点没有1个红色子节点

案例修复：

1、父节点为红色：

删除节点88，出现下溢

因为兄弟节点76没有可以借出的红色节点，所以需要父节点80来向下与76合并进行修复

将兄弟节点76染成黑色，父节点80染成黑色即可完成修复

2、父节点为黑色：

删除节点88，删除之后节点88就会出现下溢

删除之后父节点80应该向下合并进行修复，但是因为父节点80为黑色，如果向下合并之后，其实就相当于80这个节点也出现了下溢。

这个时候只需要把父节点当作被删除的节点进行处理即可

修复步骤总结：
1. 父节点向下与兄弟节点进行合并
2. 将兄弟染成红色、父节点染成黑色即可修复红黑树性质
  如果父节点是黑色，直接将父节点当成被删除的节点处理，来修复父节点的下溢情况
6.3.5 删除黑色叶子节点——删除节点的兄弟节点为红色

富国删除节点的兄弟节点为红色，这样删除节点出现下溢后没办法通过兄弟节点来进行修复。这就需要先把红黑树转换为兄弟节点为黑色的情况，就可以套用上面讲的修复方法来进行修复了。

判定条件：兄弟节点是红色

案例修复：

删除88节点之前，需要先转换成兄弟节点为黑色的情况，当前88的兄弟节点是红色55。可以将其看作LL情况，对父节点88进行右旋转，这样55就被移动上去了，成了80的父节点。76也被移动上去了，成了80的子节点。

这种情况，删除节点88的兄弟节点就变成了黑色，并且没有红色子节点，可以继续套用之前讲的方法来进行修复了。

删除掉88，将80染成黑色，76染成红色，完成修复。

修复步骤总结：
1. 兄弟节点染成 BLACK，父节点染成染成 RED，对父节点进行右旋
2. 于是又回到兄弟节点是黑色的情况（侄子节点变为兄弟节点），继续使用兄弟节点为黑色的方法进行修复
七、红黑树的平衡

AVL是靠平衡因子来保持平衡的，比如平衡因子为1，那么左右子树的高度差就不能超过1，是一种强平衡。

对于红黑树而言，为何那5条性质，就能保证红黑树是平衡的？
- 因为那5条性质，可以保证红黑树等价于4阶B树
B树比较矮，它本身就是平衡的，高度越小越平衡。

红黑树就是能保证这个树高度不会特别高，红黑树的最大高度是 2 ∗ log2(n + 1) ，依然是 O(logn) 级别，因为高度不会很大进而维持一种相对平衡的状态。相比AVL树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍。这是是一种弱平衡、黑高度平衡（黑高度只算黑色节点个数，红黑树的任何一条路径的黑色节点数一样，则黑高度都是一样）。

八、红黑树的平均时间复杂度
- 搜索：O(logn)
- 添加：O(logn)，O(1) 次的旋转操作
- 删除：O(logn)，O(1) 次的旋转操作
九、AVL树 vs 红黑树

9.1 AVL树
- 平衡标准比较严格：每个左右子树的高度差不超过1
- 最大高度是 1.44 ∗ log2 n + 2 − 1.328（100W个节点，AVL树最大树高28）
- 搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn) 次旋转调整
9.2 红黑树
- 平衡标准比较宽松：没有一条路径会大于其他路径的2倍
- 最大高度是 2 ∗ log2(n + 1)（ 100W个节点，红黑树最大树高40）
- 搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整
9.3 如何选择
- 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
- 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树
- 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树
9.4 案例对比

10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96组成一棵树

9.4.1 二叉搜索树

非常不平衡

9.4.2 AVL树

最平衡

9.4.3 红黑树

相对比较平衡

相关文章：【Java集合】HashMap系列（一）——底层数据结构分析
 【Java集合】HashMap系列（二）——底层源码分析
 【Java集合】HashMap系列（三）——TreeNode内部类源码分析
 【Java集合】一文快速了解HashMap底层原理
收起
展开全文
b树数据结构红黑树 HashMap
(002)HashMap$TreeNode之往红黑树添加元素-putTreeVal方法.docx
2020-06-18 00:48:06

HashMap之往红黑树添加元素-putTreeVal方法源码解读：当要put的元素所在数组索引位置已存在元素，且是红黑树类型时，就会调用putTreeVal方法添加元素到红黑树上，具体操作步骤如下： 1. 从根节点开始，到左右子树，...

收起
红黑树的插入与删除（改）
2020-03-20 23:21:49

红黑树的插入与删除，验证并更正了文档的一些错位。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

收起