C++實作紅黑樹

一、紅黑樹的性質

紅黑樹也是二叉搜尋樹，它的每個節點增加了一個機關用來表示顔色，可以是Red也可以是Black，通過對任意一條根到葉子節點的顔色來限制，紅黑樹保證最長路徑是最短路徑的兩倍，是以近似平衡。

紅黑樹的性質：

1、每個節點不是紅色就是黑色

2、樹的根節點是黑色

3、如果一個節點是紅色，則它的兩個孩子節點是黑色的（沒有連續的紅色）

4、對于每個結點，從該結點到其所有後代葉結點的簡單路徑上，均包含相同數目的黑色結點(每條路徑上黑色結點的數量相等）

看一下紅黑樹的節點結構：

enum COLOR
{
  BLACK,
  RED
};

template<class K, class V>
struct RBTreeNode
{
  RBTreeNode(const K& key, const V& value, COLOR color = RED)
  :_pLeft(NULL)
  , _pRight(NULL)
  , _pParent(NULL)
  , _key(key)
  , _value(value)
  , _color(color)
  {}

  RBTreeNode<K, V> *_pLeft;
  RBTreeNode<K, V> *_pRight;
  RBTreeNode<K, V> *_pParent;

  K _key;
  V _value;
  COLOR _color;
};

二、插入節點後分析

1、插入的位置若為根節點，根據性質可知調整為黑色。

2、插入節點後，違反了性質，需要做調整，可能遇到下面三種情況：

注：cur為目前節點，p為父節點，g為祖父節點，u為叔叔節點

情況一：

cur為紅，p為紅，g為黑，u存在且為紅，如下圖：

不能将p直接改為黑色，這樣會改變某路徑黑色節點的個數。

情況二：

cur為紅，p為紅，g為黑，u不存在/u為黑，如下圖，對樹g右旋：

上圖，p為g的左孩子，cur為p的左孩子，則進行右單旋轉；同理，p為g的右孩子，cur 為p的右孩子，則進行左單旋轉。

注：左旋及右旋的具體過程和AVL樹很像，隻有少了平衡因子的更新，但是多了變色處理。具體可以參考上篇AVL樹。

情況三：

cur為紅，p為紅，g為黑，u不存在/u為黑，如下圖，對樹cur左旋：

轉化為情況二，對g進行右旋。

上圖，p為g的左孩子，cur為p的右孩子，則針對p做左單旋轉；同理，p為g的右孩子， cur為p的左孩子，則針對p做右單旋轉。

插入算法代碼如下：

bool Insert(const K& key, const V& value)
  {
    if (NULL == _pRoot)
    {
      _pRoot = new Node(key, value, BLACK);   //根節點為黑色
      return true;
    }

    //找插入位置
    pNode pCur = _pRoot;
    pNode pParent = NULL;

    while (pCur)
    {
      if (key < pCur->_key)
      {
        pParent = pCur;
        pCur = pCur->_pLeft;
      }
      else if (key > pCur->_key)
      {
        pParent = pCur;
        pCur = pCur->_pRight;
      }
      else
      {
        return false;
      }
    }

    pCur = new Node(key, value);
    if (key < pParent->_key)
      pParent->_pLeft = pCur;
    else
      pParent->_pRight = pCur;

    pCur->_pParent = pParent;

    //有可能會違反紅黑樹的性質---3
    while (pParent&&pParent->_color == RED)
    {
      pNode grandParent = pParent->_pParent;
      if (pParent == grandParent->_pLeft)
      {
        pNode uncle = grandParent->_pRight;
        //情況一，叔叔節點存在且為紅
        if (uncle&&uncle->_color == RED)
        {
          pParent->_color = BLACK;
          uncle->_color = BLACK;
          grandParent->_color = RED;

          pCur = grandParent;   //繼續向上調整
          pParent = pCur->_pParent;
        }

        //叔叔不存在或者存在且為黑
        else
        {
          //若是第三種情況轉化為第二種
          if (pCur == pParent->_pRight)
          {
            RotateL(pParent);
            swap(pParent, pCur);
          }

          RotateR(grandParent);
          pParent->_color = BLACK;
          grandParent->_color = RED;
          break;
        }
      }
      //父親節點為雙親的右節點
      else
      {
        pNode uncle = grandParent->_pLeft;
        //情況一，叔叔節點存在且為紅
        if (uncle&&uncle->_color == RED)
        {
          pParent->_color = BLACK;
          uncle->_color = BLACK;
          grandParent->_color = RED;

          pCur = grandParent;   //繼續向上調整
          pParent = pCur->_pParent;
        }

        //叔叔不存在或者存在且為黑
        else
        {
          //若是第三種情況轉化為第二種
          if (pCur == pParent->_pLeft)
          {
            RotateR(pParent);
            swap(pParent, pCur);
          }

          RotateL(grandParent);
          pParent->_color = BLACK;
          grandParent->_color = RED;
        }
      }
    }
    _pRoot->_color = BLACK;
    return true;
  }

三、判斷是否為紅黑樹

根據紅黑樹的性質，根節點為黑色；要滿足任何一個路徑黑色節點的個數相等，我們可以分别統計每條黑色節點的個數，當相等時就判斷是不是紅黑樹；以及有沒有相鄰的紅色節點。

bool IsRBTree()
  {
    if (_pRoot == NULL)
      return true;
    if (_pRoot->_color == RED)  //根節點為紅色
      return false;

    int blackNum = 0;  //黑色節點的個數
    int num = 0;     //任意路徑的黑色節點個數
    pNode pCur = _pRoot;
    while (pCur)
    {
      if (pCur->_color == BLACK)
      {
        blackNum++;
      }
      pCur = pCur->_pLeft;
    }

    return _IsRBTree(_pRoot, blackNum, num);
  }

bool _IsRBTree(pNode pRoot, const int blackNum, int num)
  {
    if (NULL == pRoot)  //一條路徑結束
    {
      if (num != blackNum)
      {
        return false;
      }
      else
      {
        return true;
      }
    }
    if (pRoot->_color == BLACK)
    {
      ++num;
    }
    //兩個相鄰的紅色節點
    if ((pRoot->_color == RED) && (pRoot->_pParent->_color == RED))
    {
      return false;
    }
    return _IsRBTree(pRoot->_pLeft, blackNum, num) && _IsRBTree(pRoot->_pRight, blackNum, num);
  }

#pragma once

enum COLOR
{
  BLACK,
  RED
};

template<class K, class V>
struct RBTreeNode
{
  RBTreeNode(const K& key, const V& value, COLOR color = RED)
  :_pLeft(NULL)
  , _pRight(NULL)
  , _pParent(NULL)
  , _key(key)
  , _value(value)
  , _color(color)
  {}

  RBTreeNode<K, V> *_pLeft;
  RBTreeNode<K, V> *_pRight;
  RBTreeNode<K, V> *_pParent;

  K _key;
  V _value;
  COLOR _color;
};

template<class K, class V>
class RBTree
{
  typedef RBTreeNode<K, V> Node;
  typedef Node* pNode;
public:
  RBTree()
    :_pRoot(NULL)
  {}

  bool Insert(const K& key, const V& value)
  {
    if (NULL == _pRoot)
    {
      _pRoot = new Node(key, value, BLACK);   //根節點為黑色
      return true;
    }

    //找插入位置
    pNode pCur = _pRoot;
    pNode pParent = NULL;

    while (pCur)
    {
      if (key < pCur->_key)
      {
        pParent = pCur;
        pCur = pCur->_pLeft;
      }
      else if (key > pCur->_key)
      {
        pParent = pCur;
        pCur = pCur->_pRight;
      }
      else
      {
        return false;
      }
    }

    pCur = new Node(key, value);
    if (key < pParent->_key)
      pParent->_pLeft = pCur;
    else
      pParent->_pRight = pCur;

    pCur->_pParent = pParent;

    //有可能會違反紅黑樹的性質---3
    while (pParent&&pParent->_color == RED)
    {
      pNode grandParent = pParent->_pParent;
      if (pParent == grandParent->_pLeft)
      {
        pNode uncle = grandParent->_pRight;
        //情況一，叔叔節點存在且為紅
        if (uncle&&uncle->_color == RED)
        {
          pParent->_color = BLACK;
          uncle->_color = BLACK;
          grandParent->_color = RED;

          pCur = grandParent;   //繼續向上調整
          pParent = pCur->_pParent;
        }

        //叔叔不存在或者存在且為黑
        else
        {
          //若是第三種情況轉化為第二種
          if (pCur == pParent->_pRight)
          {
            RotateL(pParent);
            swap(pParent, pCur);
          }

          RotateR(grandParent);
          pParent->_color = BLACK;
          grandParent->_color = RED;
          break;
        }
      }
      //父親節點為雙親的右節點
      else
      {
        pNode uncle = grandParent->_pLeft;
        //情況一，叔叔節點存在且為紅
        if (uncle&&uncle->_color == RED)
        {
          pParent->_color = BLACK;
          uncle->_color = BLACK;
          grandParent->_color = RED;

          pCur = grandParent;   //繼續向上調整
          pParent = pCur->_pParent;
        }

        //叔叔不存在或者存在且為黑
        else
        {
          //若是第三種情況轉化為第二種
          if (pCur == pParent->_pLeft)
          {
            RotateR(pParent);
            swap(pParent, pCur);
          }

          RotateL(grandParent);
          pParent->_color = BLACK;
          grandParent->_color = RED;
        }
      }
    }
    _pRoot->_color = BLACK;
    return true;
  }

  bool IsRBTree()
  {
    if (_pRoot == NULL)
      return true;
    if (_pRoot->_color == RED)  //根節點為紅色
      return false;

    int blackNum = 0;  //黑色節點的個數
    int num = 0;     //任意路徑的黑色節點個數
    pNode pCur = _pRoot;
    while (pCur)
    {
      if (pCur->_color == BLACK)
      {
        blackNum++;
      }
      pCur = pCur->_pLeft;
    }

    return _IsRBTree(_pRoot, blackNum, num);
  }
  void InOrder()
  {
    if (NULL == _pRoot)
      return;
    _InOrder(_pRoot);
  }
private:
  bool _IsRBTree(pNode pRoot, const int blackNum, int num)
  {
    if (NULL == pRoot)  //一條路徑結束
    {
      if (num != blackNum)
      {
        return false;
      }
      else
      {
        return true;
      }
    }
    if (pRoot->_color == BLACK)
    {
      ++num;
    }
    //兩個相鄰的紅色節點
    if ((pRoot->_color == RED) && (pRoot->_pParent->_color == RED))
    {
      return false;
    }
    return _IsRBTree(pRoot->_pLeft, blackNum, num) && _IsRBTree(pRoot->_pRight, blackNum, num);
  }
  //左單旋
  void RotateL(pNode pParent)
  {
    pNode pSubR = pParent->_pRight;
    pNode pSubRL = pSubR->_pLeft;

    //處理pSubR
    pParent->_pRight = pSubRL;
    if (pSubRL)
      pSubRL->_pParent = pParent;

    pSubR->_pLeft = pParent;
    pNode pPParent = pParent->_pParent;
    pSubR->_pParent = pPParent;
    pParent->_pParent = pSubR;

    //判斷是否為根
    if (pParent == _pRoot)
      _pRoot = pSubR;
    //判斷是左子樹還是右子樹
    else
    {
      if (pPParent->_pLeft == pParent)
        pPParent->_pLeft = pSubR;
      else
        pPParent->_pRight = pSubR;
    }
  }

  //右單旋
  void RotateR(pNode pParent)
  {
    pNode pSubL = pParent->_pLeft;
    pNode pSubLR = pSubL->_pRight;

    //處理pSubR
    pParent->_pLeft = pSubLR;
    if (pSubLR)
      pSubLR->_pParent = pParent;

    pSubL->_pRight = pParent;
    pNode pPParent = pParent->_pParent;
    pSubL->_pParent = pPParent;
    pParent->_pParent = pSubL;

    //判斷是否為根
    if (pParent == _pRoot)
      _pRoot = pSubL;
    //判斷是左子樹還是右子樹
    else
    {
      if (pPParent->_pLeft == pParent)
        pPParent->_pLeft = pSubL;
      else
        pPParent->_pRight = pSubL;
    }
  }

  void _InOrder(pNode pRoot)
  {
    if (pRoot)
    {
      _InOrder(pRoot->_pLeft);
      cout << "<" << pRoot->_key << "," << pRoot->_color << ">" << endl;
      _InOrder(pRoot->_pRight);
    }
  }
private:
  pNode _pRoot;
};

void RBTreeTest()
{
  int array[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
  RBTree<int, int> t;
  for (size_t i = 0; i < sizeof(array) / sizeof(array[0]); i++)
  {
    t.Insert(array[i], i);
  }
  t.InOrder();

  if (t.IsRBTree())
    cout << "是紅黑樹" << endl;
  else
    cout << "不是紅黑樹" << endl;
}

C++實作紅黑樹

繼續閱讀

WCF服務配置總結

bzoj4034&luogu3178 [HAOI2015]樹上操作

luogu3384 【模闆】樹鍊剖分

bellman -ford算法的改進 spfa 算法

cf77C(樹形DP)

洛谷 P3384 【模闆】樹鍊剖分

牛客小白月賽9 A、B、C、D、E、H

洛谷 P3806 【模闆】點分治1

BZOJ 3261: 最大異或和

hiho1063(樹型dp)

計蒜客 - 子樹權值計數（DFS序+莫隊）

HDU 5524 Subtrees

FZU 1064 教授的測試

CSU 1811 Tree Intersection

圖解

PAT (Top Level) Practise 1007 Red-black Tree (35)