从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现（下）-阿里云开发者社区

从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现（上）：https://developer.aliyun.com/article/1522282

3.4 红黑树插入完整代码

（旋转还是用AVL树写的旋转，把平衡因子删掉，所以只需复制两个单旋）

  bool Insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      _root->_col = BLACK; // 根给黑色
      return true;
    }
 
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) // 找到要插入的结点
    {
      if (cur->_kv.first < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return false;
      }
    }
 
    cur = new Node(kv);
    cur->_col = RED; // 默认插入红色结点
    if (parent->_kv.first < kv.first) // 找到位置后插入结点
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
 
    while (parent && parent->_col == RED) // 父亲存在且为红才需要处理
    {
      Node* grandfather = parent->_parent;
      assert(grandfather); // 确定的可以断言下，否则就是插入前就不是红黑树
      assert(grandfather->_col == BLACK);
      if (grandfather->_left == parent)
      {
        Node* uncle = grandfather->_right;
 
        if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红(可以直接复制到下面uncle在左边)
        {    // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三：叔叔存在且为黑或叔叔不存在
        {
          if(cur == parent->_left) // 情况二的右旋+变色(parent在左)
          {
            //     g      
            //   p   u
            // c
            RotateR(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的左右双旋+变色(parent在左)
          {
            //      g      
                        //   p     u
                        //    c
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
 
        if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红
        {    // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三：叔叔存在且为黑或叔叔不存在
        {
          if (cur == parent->_right) // 情况二的左旋+变色(parent在右)
          {
            //     g      
            //   u   p
            //        c
            RotateL(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的右左双旋+变色(parent在右)
          {
            //       g      
            //    u     p
            //         c
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    
    _root->_col = BLACK;
    return true;
  }

4. 红黑树的验证和完整代码

4.1 验证是不是搜索树：

  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
 
protected:
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }

先拿AVL树的测试过来，Test.c:

#include "RedBlackTree.h"
 
void TestRBTree1()
{
  //int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
  RBTree<int, int> t1;
  for (const auto& e : arr)
  {
    t1.Insert(make_pair(e, e));
  }
 
  t1.InOrder();
  //cout << "IsBalance:" << t1.IsBalance() << endl;
}
 
int main()
{
  TestRBTree1();
 
  return 0;
}

4.2 验证是不是红黑树：

但中序有序只能证明是二叉搜索树，给你验证一颗树是不是红黑树你会怎么验证？是验证最长路径不超过最短路径的两倍还是红黑树的那几条性质？

要证明二叉树是红黑树还需验证该二叉树是否满足红黑树的性质。因为最长路径不超过最短路径的两倍也不能保证是红黑树，只有满足全部红黑树的性质的才是。

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个空结点都是黑色的（这里的空结点也叫NIL结点，只是为了方便知道有多少条路径）

第一条，枚举就能保证。
第二条，红色就false，一句代码解决。
第三条，我们可以遍历这颗树，用逆向思维，遇到红色结点就反过来判断它的父亲是不是红色的。

第四条，我们可以用前序遍历，遍历第一遍的时候保存黑色结点个数，后面不同就false。
第五条，不用管。

4.3 红黑树完整代码：

RedBlackTree.h：

#pragma once
 
#include <iostream>
#include <assert.h>
#include <time.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; // 比AVL树少了平衡因子，多了颜色
 
  RBTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
  {}
};
 
template<class K, class V>
struct RBTree
{
  typedef RBTreeNode<K, V> Node;
public:
  bool Insert(const pair<K, V>& kv)
  {
    if (_root == nullptr)
    {
      _root = new Node(kv);
      _root->_col = BLACK; // 根给黑色
      return true;
    }
 
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) // 找到要插入的结点
    {
      if (cur->_kv.first < kv.first)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (cur->_kv.first > kv.first)
      {
        parent = cur;
        cur = cur->_left;
      }
      else
      {
        return false;
      }
    }
 
    cur = new Node(kv);
    cur->_col = RED; // 默认插入红色结点
    if (parent->_kv.first < kv.first) // 找到位置后插入结点
    {
      parent->_right = cur;
    }
    else
    {
      parent->_left = cur;
    }
    cur->_parent = parent;
 
    while (parent && parent->_col == RED) // 父亲存在且为红才需要处理
    {
      Node* grandfather = parent->_parent;
      assert(grandfather); // 确定的可以断言下，否则就是插入前就不是红黑树
      assert(grandfather->_col == BLACK);
      if (grandfather->_left == parent)
      {
        Node* uncle = grandfather->_right;
 
        if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红(可以直接复制到下面uncle在左边)
        {    // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三：叔叔存在且为黑或叔叔不存在
        {
          if(cur == parent->_left) // 情况二的右旋+变色(parent在左)
          {
            //     g      
            //   p   u
            // c
            RotateR(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的左右双旋+变色(parent在左)
          {
            //      g      
                        //   p     u
                        //    c
            RotateL(parent);
            RotateR(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
      else
      {
        Node* uncle = grandfather->_left;
 
        if (uncle && uncle->_col == RED) // 情况一，叔叔存在且为红
        {    // 将父亲和叔叔改为黑，祖父改为红，然后把祖父当成cur，parent变祖父parent继续向上调整。
          parent->_col = uncle->_col = BLACK;
          grandfather->_col = RED;
          cur = grandfather;
          parent = cur->_parent;
        }
        else // 情况二或情况三：叔叔存在且为黑或叔叔不存在
        {
          if (cur == parent->_right) // 情况二的左旋+变色(parent在右)
          {
            //     g      
            //   u   p
            //        c
            RotateL(grandfather);
            parent->_col = BLACK; // 父亲变为根了
            grandfather->_col = RED;
          }
          else // 情况二的右左双旋+变色(parent在右)
          {
            //       g      
            //    u     p
            //         c
            RotateR(parent);
            RotateL(grandfather);
            cur->_col = BLACK; // cur变为根了
            grandfather->_col = RED;
          }
          break;
        }
      }
    }
    
    _root->_col = BLACK;
    return true;
  }
 
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
 
  bool IsBalance()
  {
    if (_root == nullptr)
    {
      return true;
    }
 
    if (_root->_col == RED) // 验证性质二
    {
      cout << "根节点不是黑色" << endl;
      return false;
    }
 
    int benchmark = 0; // 黑色节点数量基准值
    //Node* cur = _root; // 这种方法是先遍历一遍，然后传值，不过我们可以传引用
    //while (cur)
    //{
    //  if (cur->_col == BLACK)
    //  {
    //    ++benchmark;
    //  }
    //  cur = cur->_left;
    //}
    return PrevCheck(_root, 0, benchmark); // 验证性质三和四
  }
 
protected:
  bool PrevCheck(Node* root, int blackNum, int& benchmark)
  {
    if (root == nullptr)
    {
      if (benchmark == 0)
      {
        benchmark = blackNum;
        return true;
      }
 
      if (blackNum != benchmark) // 验证性质三
      {
        cout << "某条黑色节点的数量不相等" << endl;
        return false;
      }
      else
      {
        return true;
      }
    }
 
    if (root->_col == BLACK)
    {
      ++blackNum;
    }
 
    if (root->_col == RED && root->_parent->_col == RED) // 验证性质四
    {
      cout << "存在连续的红色节点" << endl;
      return false;
    }
 
    return PrevCheck(root->_left, blackNum, benchmark)
      && PrevCheck(root->_right, blackNum, benchmark);
  }
 
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }
 
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right; // 动了三个标记了的结点，共更新六个指针，这更新两个指针
    Node* subRL = subR->_left;
 
    parent->_right = subRL;
    if (subRL) // subRL不为空才更新
    {
      subRL->_parent = parent;
    }
 
    Node* ppNode = parent->_parent; // 记录parent的parent，防止parent是一颗子树的头结点
 
    subR->_left = parent; // 再更新两个指针
    parent->_parent = subR;
 
    if (_root == parent)  // 最后更新两个指针
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else // parent是一颗子树的头结点
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subR;
      }
      else
      {
        ppNode->_right = subR;
      }
      subR->_parent = ppNode;
    }
  }
 
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
 
    parent->_left = subLR; // 更新两个节点
    if (subLR)
    {
      subLR->_parent = parent;
    }
 
    Node* ppNode = parent->_parent;
 
    subL->_right = parent; // 再更新两个节点
    parent->_parent = subL;
 
    if (_root == parent) // 最后更新两个结点
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subL;
      }
      else
      {
        ppNode->_right = subL;
      }
 
      subL->_parent = ppNode;
    }
  }
 
  Node* _root = nullptr;
};

Test.c:

#include "RedBlackTree.h"
 
void TestRBTree1()
{
  //int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
  RBTree<int, int> t1;
  for (const auto& e : arr)
  {
    t1.Insert(make_pair(e, e));
  }
 
  t1.InOrder();
  cout << "IsBalance:" << t1.IsBalance() << endl;
}
 
void TestRBTree2()
{
  size_t N = 10000;
  srand(time(0));
  RBTree<int, int> t1;
  for (size_t i = 0; i < N; ++i)
  {
    int x = rand();
    cout << "Insert:" << x << ":" << i << endl;
    t1.Insert(make_pair(x, i));
  }
  cout << "IsBalance:" << t1.IsBalance() << endl;
}
 
int main()
{
  TestRBTree2();
 
  return 0;
}

5. 红黑树笔试选择题

1.关于红黑树以下说法正确的是（）

A.空树不是红黑树，因为红黑树要求根节点必须为黑色，而空树中没有根节点

B.红黑树也是二叉搜索树，因此其按照前序遍历可以得到有序序列

C.红黑树是一棵真正平衡的二叉树

D.红黑树最长路径中节点个数可能会等于最短路径中节点个数的两倍

2. 红黑树的插入算法复杂度最坏情况是（）

A.O(n)

B.O(log(n))

C.O(nlog(n))

D.其他都不对

3. 下面关于红黑树的特性说法错误的是（）

A.红黑树最左侧节点一定是最小的，最右侧节点一定是最大的

B.红黑树在实现时必须要有头结点

C.红黑树中可能会出现连在一起的黑色节点

D.红黑树的旋转不需要依靠平衡因子

4. 关于AVL树和红黑树的区别说法不正确的是（）

A.AVL树和红黑树保证平衡性的方式不同

B.AVL树和红黑树都是平衡树，因此查找的时间复杂度都是O(log_2N)

C.AVL树和红黑树的性质遭到破坏时，都需要进行旋转

D.AVL树和红黑树中序遍历都可以得到有序序列，因为它们都是二叉搜索树

答案：

1. D

A：错误，空树也是红黑树，性质5中规定树中的空指针域为叶子节点，因此空树也是有节点的

B：错误，红黑树也是二叉搜索树，按照中序遍历才可以得到有序序列

C：红黑树不像AVL树那么严格，是一棵近似平衡的二叉搜索树

D：正确，比如红黑树中只有两个节点

2. B

红黑树是近似的平衡树，没有什么最坏情况，插入的时间复杂度为O(log(N))

3. B

A：该题不严谨，这个取决于红黑树中元素的比较规则，最左侧节点可能是最大的，也可能是最小的，没有规定，取决于创建树时的比较方式

B：错误，红黑树在实现时可以没有头节点，这个根据需要是否给出这里头结点和带头双向顺序链表的差不多（我们实现的红黑树就没有）

C：正确，但是一定不能出现连在一起的红色节点

D：正确，红黑树是通过节点颜色以及红黑树的性质来保证其平衡性的，AVL树需要平衡因子保证

4. C

A：正确，AVL树通过节点的平衡因子保证，红黑树通过节点的颜色以及红黑树的特性保证

B：正确，AVL树是严格平衡的，红黑树虽然是近似平衡，但其性能往往比AVL树好，而且实现简单，因此他们的查找效率都是O(logN)

C：错误，AVL树是一定需要旋转，红黑树不一定，红黑树有时只需要改变节点的颜色即可

D：正确，参考概念

6. 红黑树的零碎知识

红黑树的删除和AVL树一样不做讲解，有兴趣可参考《STL源码剖析》

红黑树与AVL树的比较

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

红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数。所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树插入动图

1. 以升序插入构建红黑树

2. 以降序插入构建红黑树

随机插入的找不到动图了，放个图片看看：（都是一样保持基本平衡的）

红黑树的应用

1. C++ STL库 -- map / set、mutil_map / mutil_set

2. Java 库

3. linux内核

4. 其他一些库

本篇完。

下一篇：改造红黑树用来封装set和map（红黑树迭代器的实现），再下一篇：哈希。

从C语言到C++_28(红黑树RedBlackTree)概念+插入接口实现（下）

3.4 红黑树插入完整代码

4. 红黑树的验证和完整代码

4.1 验证是不是搜索树：

4.2 验证是不是红黑树：

4.3 红黑树完整代码：

5. 红黑树笔试选择题

答案：

6. 红黑树的零碎知识

本篇完。

热门文章

最新文章

相关课程

相关电子书