防城港市网站建设_网站建设公司_云服务器_seo优化

本篇会用到上篇【AVL树的实现】中的旋转知识。

一，红黑树的概念

红黑树是一颗二叉搜索树，它的每一个节点增加一个存储为来表示节点的颜色。可以是红色或者黑色。它通过对从根开始到叶子节点的每条路径上各个节点颜色的约束，确保最长路径不会超过最短路径的2倍，从而实现平衡的。

1.1，红黑树的规则

1，每个节点不是红色就是黑色。 2，根节点是黑色的。 3，红色节点的两个孩子只能是 黑色节点或者是空节点。也就是说不能出现连续的红色节点 4，对于任意一个节点，从该节点开始，到叶子节点的所有路径上，均包含相同数量的黑色节点。

以上 都是红黑树，满足红黑树的规则。

1.2，红黑树的最长路径

1，由第四条规则可知，从根节点开始的每条路径上，黑色节点的数量相同。所以在极端场景下，一颗红黑树，它的最短路径就是节点全为黑色的路径。假设红黑树的每条路径黑色节点数量都为b,那么最短路径的节点数量为b.

2，由 第三条规则可知，一条路径上不能由连续的红色节点，最长路径是由一黑一红间隔组成的，所以最长路径为2*b。

3，而对于一颗红黑树，最长和最短路径不一定存在。我们可以得出对于任意一颗红黑树，它的任意 一条路径长度x都是，b<=x<=2*b.

1.3，红黑树的效率分析

假设N是红黑树节点的数量，h是最短路径的长度,最长路径不超过2*h

可以得到2^h-1<= N <= 2^(2*h)-1,推出h大致为logN,也就意味着红黑树的增删查该最坏走2*logN,时间复杂度O(logN).

二，红黑树的实现

2.1，红黑树的结构

enum color { Red, Black }; template<class k,class v> struct RBTreeNode { RBTreeNode(const pair<k,v>& kv) :_left(nullptr) ,_right(nullptr) ,_parent(nullptr) ,_kv(kv) {} RBTreeNode<k, v>* _left; RBTreeNode<k, v>* _right; RBTreeNode<k, v>* _parent; pair<k, v> _kv; color _col; }; template<class k,class v> class RBTree { typedef RBTreeNode<k, v> Node; public: //... private: Node* _root=nullptr; };

2.2，红黑树的插入

2.2.1，大致过程

1，插入一个值需要按照搜索树的规则进行插入，再判断插入后是否满足红黑树的规则。2，如果是空树插入，新增节点就是黑色节点。如果是非空树插入，新增节点就必须是红色节点，因为如果插入黑色节点，就一定会破坏规则4，而插入红色节点是有可能会破坏规则3，而且对于规则3来说，解决方法比规则4的解决方法容易。3，非空树插入后，如果父节点是黑色节点，则没有违反任何规则，插入结束。 4，非空树插入后，如果父节点是红色节点，则违反规则3，进一步分析。