HOWTO · C++

C++ のレッドブラックツリー

このチュートリアルでは、C++ の赤黒木について説明します。

著者 Sheeraz Gul公開日 2023-06-20更新日 2024-02-15

このチュートリアルでは、C++ の赤黒木について説明します。

C++ のレッドブラックツリー

赤黒ツリーは、ノードの色を示す個別のプロパティが各ノードに含まれている場合に使用される、自己均衡二分探索ツリーと見なされます。赤黒には、次の 5つのプロパティがあります。

赤/黒 プロパティ - ツリー内のすべてのノードは、赤または黒のいずれかで色付けされます。
Root プロパティ - ルートは常に黒です。
Leaf プロパティ - すべての葉 (NIL) は常に黒です。
Red プロパティ - すべての赤ノードの子は、黒である必要があります。
Depth プロパティ - あるノードから別の子孫リーフへのパスは、黒ノードの数と同じ黒深度平均を持ちます。

上記の条件がどこにも満たされない場合、その木は赤黒の木にはなりません。下図の赤黒木の構造を見てください。

赤黒の木

ご覧のとおり、各ノードには、ルートノードを除いて、colour、key、left child、right child、および parent があります。

上記のプロパティから、ノードの色の制限により、ルートからリードまでのパスが 2 倍を超えないようにするため、赤黒ツリーは自己均衡ツリーであることが意図されており、ツリーの維持に役立ちます。自分自身のバランスをとります。

赤黒木の部分木の回転

ローテーションでは、サブツリーのノードの位置が交換されます。これは、挿入や削除などの他の操作によって影響を受ける赤黒ツリーのプロパティを維持するために使用されます。ローテーションのタイプは次のとおりです。

Left Rotate - このタイプのローテーションでは、右側のノードの配置が左側のノードの配置に変換されます。
Right Rotate - このタイプのローテーションでは、左側のノードの配置が右側のノードの配置に変換されます。
Left-Right Rotate - このタイプの回転では、配置は最初に左に移動し、次に右に移動します。
Right-Left Rotate - このタイプの回転では、配置は最初に右に移動し、次に左に移動します。
Recolor - recolor では、ノードの色を反転します。たとえば、ノードが赤の場合は黒になり、その逆も同様です。

挿入

次の手順に従って、赤黒ツリーにノードを挿入します。

通常の BST 操作を使用してノードを挿入します。
挿入した node-red に色を付けます。
最後に、挿入が赤黒ツリーのプロパティに違反していないかどうかを確認します。もしそうなら、それを修正する必要があります。

赤黒木に挿入するための擬似コードを次に示します。

RB - INSERT(Tree, n) BST -
        INSERT(Tree, n)  // ordinary BST insertion
        while n.parent.color
    == RED if n.parent == n.parent.parent.right u =
    n.parent.parent
        .left  // uncle
    if u.color
    == RED u.color = BLACK n.parent.color = BLACK n.parent.parent.color =
        RED n = n.parent.parent else if n == n.parent.left n =
                    n.parent LEFT -
                    ROTATE(Tree,
                           n) n.parent.color = BLACK n.parent.parent.color =
                        RED RIGHT -
                        ROTATE(Tree, n.parent.parent) else(
                            same with "left" and
                            "right" exchanged) Tree.root.color = BLACK

消す

削除操作は、挿入よりも少し複雑です。ノードを削除するには、最初に BST の削除に従う必要があります。これにより、ノードが単一の子ノードまたはリーフノードのいずれかになります。

以下の擬似コードは、赤黒木での削除操作を示しています。

RB-DELETE(Tree, n)
     BST-DELETE(Tree, n)
     while n ≠ Tree.root and n.color == BLACK
         if n == n.parent.left
             s = n.parent.right
             if s.color == RED
                 s.color = BLACK
                 n.parent.color = RED
                 LEFT-ROTATE(Tree, n.parent)
                 s = n.parent.right
             if s.left.color == BLACK and s.right.color == BLACK
                 s.color = RED
                 n = n.parent
             else if s.right.color == BLACK
                     s.left.color = BLACK
                     s.color = RED
                     RIGHT-ROTATE(Tree, s)
                     s = n.parent.right
                 s.color = n.parent.right
                 n.parent.color = BLACK
                 s.right.color = BLACK
                 LEFT-ROTATE(Tree, n.parent)
                 n = Tree.root
         else (same as with "right" and "left" exchanged)
     n.color = BLACK

赤黒木の回転、挿入、削除が理解できたので、C++ で実装してみましょう。

#include <iostream>
using namespace std;

struct Node {
  int NodeData;
  Node *parentNode;
  Node *leftNode;
  Node *rightNode;
  int NodeColor;
};

typedef Node *NodePtr;

class REDBLACKTREE {
 private:
  NodePtr root;
  NodePtr TNULL;

  void INITIALIZENULLNode(NodePtr node, NodePtr parentNode) {
    node->NodeData = 0;
    node->parentNode = parentNode;
    node->leftNode = nullptr;
    node->rightNode = nullptr;
    node->NodeColor = 0;
  }

  // The Preorder
  void PREORDERHELPER(NodePtr node) {
    if (node != TNULL) {
      cout << node->NodeData << " ";
      PREORDERHELPER(node->leftNode);
      PREORDERHELPER(node->rightNode);
    }
  }

  // The Inorder
  void INORDERHELPER(NodePtr node) {
    if (node != TNULL) {
      INORDERHELPER(node->leftNode);
      cout << node->NodeData << " ";
      INORDERHELPER(node->rightNode);
    }
  }

  // the Post order
  void POSTORDERHELPER(NodePtr node) {
    if (node != TNULL) {
      POSTORDERHELPER(node->leftNode);
      POSTORDERHELPER(node->rightNode);
      cout << node->NodeData << " ";
    }
  }

  NodePtr SEARCHTREEHELPER(NodePtr node, int key) {
    if (node == TNULL || key == node->NodeData) {
      return node;
    }

    if (key < node->NodeData) {
      return SEARCHTREEHELPER(node->leftNode, key);
    }
    return SEARCHTREEHELPER(node->rightNode, key);
  }

  // For balancing the tree after deletion
  void DELETEFIX(NodePtr x) {
    NodePtr s;
    while (x != root && x->NodeColor == 0) {
      if (x == x->parentNode->leftNode) {
        s = x->parentNode->rightNode;
        if (s->NodeColor == 1) {
          s->NodeColor = 0;
          x->parentNode->NodeColor = 1;
          LEFTROTATE(x->parentNode);
          s = x->parentNode->rightNode;
        }

        if (s->leftNode->NodeColor == 0 && s->rightNode->NodeColor == 0) {
          s->NodeColor = 1;
          x = x->parentNode;
        } else {
          if (s->rightNode->NodeColor == 0) {
            s->leftNode->NodeColor = 0;
            s->NodeColor = 1;
            RIGHTNODEROTATE(s);
            s = x->parentNode->rightNode;
          }

          s->NodeColor = x->parentNode->NodeColor;
          x->parentNode->NodeColor = 0;
          s->rightNode->NodeColor = 0;
          LEFTROTATE(x->parentNode);
          x = root;
        }
      } else {
        s = x->parentNode->leftNode;
        if (s->NodeColor == 1) {
          s->NodeColor = 0;
          x->parentNode->NodeColor = 1;
          RIGHTNODEROTATE(x->parentNode);
          s = x->parentNode->leftNode;
        }

        if (s->rightNode->NodeColor == 0 && s->rightNode->NodeColor == 0) {
          s->NodeColor = 1;
          x = x->parentNode;
        } else {
          if (s->leftNode->NodeColor == 0) {
            s->rightNode->NodeColor = 0;
            s->NodeColor = 1;
            LEFTROTATE(s);
            s = x->parentNode->leftNode;
          }

          s->NodeColor = x->parentNode->NodeColor;
          x->parentNode->NodeColor = 0;
          s->leftNode->NodeColor = 0;
          RIGHTNODEROTATE(x->parentNode);
          x = root;
        }
      }
    }
    x->NodeColor = 0;
  }

  void RBTRANSPLANT(NodePtr u, NodePtr v) {
    if (u->parentNode == nullptr) {
      root = v;
    } else if (u == u->parentNode->leftNode) {
      u->parentNode->leftNode = v;
    } else {
      u->parentNode->rightNode = v;
    }
    v->parentNode = u->parentNode;
  }

  void DELETENODEHELPER(NodePtr node, int key) {
    NodePtr z = TNULL;
    NodePtr x, y;
    while (node != TNULL) {
      if (node->NodeData == key) {
        z = node;
      }

      if (node->NodeData <= key) {
        node = node->rightNode;
      } else {
        node = node->leftNode;
      }
    }

    if (z == TNULL) {
      cout << "The Key is not found in the tree" << endl;
      return;
    }

    y = z;
    int y_original_NodeColor = y->NodeColor;
    if (z->leftNode == TNULL) {
      x = z->rightNode;
      RBTRANSPLANT(z, z->rightNode);
    } else if (z->rightNode == TNULL) {
      x = z->leftNode;
      RBTRANSPLANT(z, z->leftNode);
    } else {
      y = minimum(z->rightNode);
      y_original_NodeColor = y->NodeColor;
      x = y->rightNode;
      if (y->parentNode == z) {
        x->parentNode = y;
      } else {
        RBTRANSPLANT(y, y->rightNode);
        y->rightNode = z->rightNode;
        y->rightNode->parentNode = y;
      }

      RBTRANSPLANT(z, y);
      y->leftNode = z->leftNode;
      y->leftNode->parentNode = y;
      y->NodeColor = z->NodeColor;
    }
    delete z;
    if (y_original_NodeColor == 0) {
      DELETEFIX(x);
    }
  }

  // balance the tree after insertion
  void INSERTFIX(NodePtr k) {
    NodePtr u;
    while (k->parentNode->NodeColor == 1) {
      if (k->parentNode == k->parentNode->parentNode->rightNode) {
        u = k->parentNode->parentNode->leftNode;
        if (u->NodeColor == 1) {
          u->NodeColor = 0;
          k->parentNode->NodeColor = 0;
          k->parentNode->parentNode->NodeColor = 1;
          k = k->parentNode->parentNode;
        } else {
          if (k == k->parentNode->leftNode) {
            k = k->parentNode;
            RIGHTNODEROTATE(k);
          }
          k->parentNode->NodeColor = 0;
          k->parentNode->parentNode->NodeColor = 1;
          LEFTROTATE(k->parentNode->parentNode);
        }
      } else {
        u = k->parentNode->parentNode->rightNode;

        if (u->NodeColor == 1) {
          u->NodeColor = 0;
          k->parentNode->NodeColor = 0;
          k->parentNode->parentNode->NodeColor = 1;
          k = k->parentNode->parentNode;
        } else {
          if (k == k->parentNode->rightNode) {
            k = k->parentNode;
            LEFTROTATE(k);
          }
          k->parentNode->NodeColor = 0;
          k->parentNode->parentNode->NodeColor = 1;
          RIGHTNODEROTATE(k->parentNode->parentNode);
        }
      }
      if (k == root) {
        break;
      }
    }
    root->NodeColor = 0;
  }

  void PRINTHELPER(NodePtr root, string indent, bool last) {
    if (root != TNULL) {
      cout << indent;
      if (last) {
        cout << "R-----";
        indent += "    ";
      } else {
        cout << "L-----";
        indent += "|   ";
      }

      string sNodeColor = root->NodeColor ? "RED" : "BLACK";
      cout << root->NodeData << "(" << sNodeColor << ")" << endl;
      PRINTHELPER(root->leftNode, indent, false);
      PRINTHELPER(root->rightNode, indent, true);
    }
  }

 public:
  REDBLACKTREE() {
    TNULL = new Node;
    TNULL->NodeColor = 0;
    TNULL->leftNode = nullptr;
    TNULL->rightNode = nullptr;
    root = TNULL;
  }

  void preorder() { PREORDERHELPER(this->root); }

  void inorder() { INORDERHELPER(this->root); }

  void postorder() { POSTORDERHELPER(this->root); }

  NodePtr searchTree(int k) { return SEARCHTREEHELPER(this->root, k); }

  NodePtr minimum(NodePtr node) {
    while (node->leftNode != TNULL) {
      node = node->leftNode;
    }
    return node;
  }

  NodePtr maximum(NodePtr node) {
    while (node->rightNode != TNULL) {
      node = node->rightNode;
    }
    return node;
  }

  NodePtr successor(NodePtr x) {
    if (x->rightNode != TNULL) {
      return minimum(x->rightNode);
    }

    NodePtr y = x->parentNode;
    while (y != TNULL && x == y->rightNode) {
      x = y;
      y = y->parentNode;
    }
    return y;
  }

  NodePtr predecessor(NodePtr x) {
    if (x->leftNode != TNULL) {
      return maximum(x->leftNode);
    }

    NodePtr y = x->parentNode;
    while (y != TNULL && x == y->leftNode) {
      x = y;
      y = y->parentNode;
    }

    return y;
  }

  void LEFTROTATE(NodePtr x) {
    NodePtr y = x->rightNode;
    x->rightNode = y->leftNode;
    if (y->leftNode != TNULL) {
      y->leftNode->parentNode = x;
    }
    y->parentNode = x->parentNode;
    if (x->parentNode == nullptr) {
      this->root = y;
    } else if (x == x->parentNode->leftNode) {
      x->parentNode->leftNode = y;
    } else {
      x->parentNode->rightNode = y;
    }
    y->leftNode = x;
    x->parentNode = y;
  }

  void RIGHTNODEROTATE(NodePtr x) {
    NodePtr y = x->leftNode;
    x->leftNode = y->rightNode;
    if (y->rightNode != TNULL) {
      y->rightNode->parentNode = x;
    }
    y->parentNode = x->parentNode;
    if (x->parentNode == nullptr) {
      this->root = y;
    } else if (x == x->parentNode->rightNode) {
      x->parentNode->rightNode = y;
    } else {
      x->parentNode->leftNode = y;
    }
    y->rightNode = x;
    x->parentNode = y;
  }

  // Inserting a node
  void INSERTNODE(int key) {
    NodePtr node = new Node;
    node->parentNode = nullptr;
    node->NodeData = key;
    node->leftNode = TNULL;
    node->rightNode = TNULL;
    node->NodeColor = 1;

    NodePtr y = nullptr;
    NodePtr x = this->root;

    while (x != TNULL) {
      y = x;
      if (node->NodeData < x->NodeData) {
        x = x->leftNode;
      } else {
        x = x->rightNode;
      }
    }

    node->parentNode = y;
    if (y == nullptr) {
      root = node;
    } else if (node->NodeData < y->NodeData) {
      y->leftNode = node;
    } else {
      y->rightNode = node;
    }

    if (node->parentNode == nullptr) {
      node->NodeColor = 0;
      return;
    }

    if (node->parentNode->parentNode == nullptr) {
      return;
    }

    INSERTFIX(node);
  }

  NodePtr getRoot() { return this->root; }

  void DELETENODE(int NodeData) { DELETENODEHELPER(this->root, NodeData); }

  void printTree() {
    if (root) {
      PRINTHELPER(this->root, "", true);
    }
  }
};

int main() {
  REDBLACKTREE DEMOBST;
  DEMOBST.INSERTNODE(51);
  DEMOBST.INSERTNODE(44);
  DEMOBST.INSERTNODE(62);
  DEMOBST.INSERTNODE(34);
  DEMOBST.INSERTNODE(85);
  DEMOBST.INSERTNODE(54);

  DEMOBST.printTree();
  cout << endl << "After deleting" << endl;
  DEMOBST.DELETENODE(62);
  DEMOBST.printTree();
}

上記のコードは、赤黒ツリーを作成し、挿入、削除、および回転操作を適用します。

出力：

R-----51(BLACK)
    L-----44(BLACK)
    |   L-----34(RED)
    R-----62(BLACK)
        L-----54(RED)
        R-----85(RED)

After deleting
R-----51(BLACK)
    L-----44(BLACK)
    |   L-----34(RED)
    R-----85(BLACK)
        L-----54(RED)

著者について

Sheeraz Gul

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.

著者プロフィールを見る

C++ のレッド ブラック ツリー

赤黒木の部分木の回転

挿入

消す

Sheeraz Gul

C++ のレッドブラックツリー