乐趣区

关于c++:红黑树

jiezi

红黑树概念

  • 红黑树是一种二叉搜寻树，在每个节点上减少一个存储位，用来存储节点色彩（红或黑）
  • 通过对通过对色彩的限度，确保任意一条从根节点到叶子节点的门路不会比其余门路长出两倍（即最长门路最多只能是最短门路的两倍）
  • 红黑树通过对色彩的管制，从而达到近似均衡（AVL 是严格均衡的）
  • AVL 树通过旋转形式来管制均衡，而其搜寻效率上跟红黑树差不多（红黑树效率要略低）
  • 尽管红黑树效率略低，然而 AVL 树旋转次数过多，综合来说红黑树更好一些。

红黑树性质

  1. 每个节点只能是红色或者彩色。
  2. 根节点是彩色。
  3. 如果一个节点是红色，那么它的两个子节点就是彩色（如果一个节点是彩色，那么它的子节点能够是红色也能够是彩色）（即不存在间断的红色节点）
  4. 对于每个节点，从该节点到其后辈的所有叶子节点的门路上，每条门路的彩色节点数雷同（包含最初的空节点）
  5. 所有的空节点都是彩色。
  • 通过上述规定的管制，就能够保障红黑树的最长门路中节点个数不会超过最短门路节点数的两倍。
  • 最长门路一黑一红，最短门路全黑。

红黑树节点定义形式

  • 个别在插入新节点时，默认插入节点色彩为红色，因为默认为彩色节点，肯定会毁坏规定四，影响较大，然而默认为红色节点，只是有可能毁坏规定三。
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)   // 默认节点色彩为红色
    {}};

红黑树新增节点的三种状况

  • cur 为新增节点，p 为父节点，g 为祖父节点，u 为叔叔节点（要害看叔叔节点的色彩）
  • 蓝色方框为红黑子树。

状况一：cur 为红（在 p 的左右皆可），p 为红，g 为黑，u 存在且为红

  • 解决办法：变色
  • 将父节点和叔叔节点都变为黑，并且将祖父节点变为红
  • 如果祖父节点的父节点也为红，违反规定三，则持续向上进行变换。
  • 如果祖父节点为根节点，违反规定二，则再将祖父节点变为黑。

状况二：cur 为红，且在 p 的右边，p 为红，g 为黑，u 不存在或者存在且为黑

  • cur 在父节点的右边。
  • 解决办法：单右旋 + 变色（祖孙三代是直线关系）
  • 进行右单旋转
  • 将父节点变为黑，祖父节点变为红。

状况三：cur 为红，且在 p 的左边，p 为红，g 为黑，u 不存在或者存在且为黑

  • 解决办法：双旋转 + 变色（祖孙三代是折线关系）
  • 先进行左单旋，再进行右单旋，最初再变色。

源码地址

gitee：https://gitee.com/BJFyfwl/Lin…

退出移动版