C++의 레드 블랙 트리

Sheeraz Gul 2024년2월15일

C++ C++ Tree

이 튜토리얼은 C++의 레드-블랙 트리를 보여줍니다.

C++의 레드 블랙 트리

레드-블랙 트리는 각 노드가 노드의 색상을 나타내는 고유 속성을 포함하는 경우 사용되는 자체 균형 이진 검색 트리로 간주됩니다. Red-Black에는 다음과 같은 다섯 가지 속성이 있습니다.

빨간색/검은색 속성 - 트리의 모든 노드는 빨간색 또는 검은색으로 표시됩니다.
루트 속성 - 루트는 항상 검은색입니다.
리프 속성 - 모든 리프(NIL)는 항상 검은색입니다.
빨간색 속성 - 모든 빨간색 노드 자식이 있는 경우 검은색이어야 합니다.
Depth 속성 - 한 노드에서 다른 자손 리프까지의 모든 경로는 블랙 노드의 수와 동일한 블랙 깊이 수단을 갖습니다.

위의 조건이 충족되지 않으면 해당 트리는 레드 블랙 트리가 될 수 없습니다. 아래 그림에서 red-black 트리의 구조를 참조하십시오.

레드 블랙 트리

보시다시피 루트 노드를 제외한 각 노드에는 색상, 키, 왼쪽 자식, 오른쪽 자식 및 부모가 있습니다.

위의 속성에서 레드-블랙 트리는 노드 색상의 제한으로 인해 루트에서 리드까지의 경로가 두 번 이상 길지 않아 트리가 유지하는 데 도움이 되기 때문에 자체 균형 트리가 됩니다. 스스로 균형을 잡습니다.

Red-Black 트리에서 하위 트리의 회전

교체 시 하위 트리 노드의 위치가 서로 바뀌는데, 이는 삽입 및 삭제와 같은 다른 작업의 영향을 받기 때문에 red-black 트리의 속성을 유지하는 데 사용됩니다. 회전 유형은 다음과 같습니다.

왼쪽 회전 - 이 유형의 회전에서는 오른쪽의 노드 배열이 왼쪽 노드의 배열로 변환됩니다.
오른쪽 회전 - 이 유형의 회전에서는 왼쪽의 노드 배열이 오른쪽 노드의 배열로 변환됩니다.
왼쪽-오른쪽 회전 - 이 유형의 회전에서는 배열이 먼저 왼쪽으로 이동한 다음 오른쪽으로 이동합니다.
오른쪽-왼쪽 회전 - 이 유형의 회전에서는 정렬이 먼저 오른쪽으로 이동한 다음 왼쪽으로 이동합니다.
재색상 - 재색상에서 노드의 색상을 뒤집습니다. 예를 들어 노드가 빨간색이면 검은색이 되거나 그 반대가 됩니다.

삽입

레드-블랙 트리에 노드를 삽입하려면 아래 단계를 따르십시오.

일반 BST 작업을 사용하여 노드를 삽입합니다.
삽입된 노드를 빨간색으로 색칠합니다.
마지막으로 삽입이 레드-블랙 트리 속성을 위반했는지 확인합니다. 만약 그렇다면, 우리는 그것을 고쳐야 합니다.

다음은 레드-블랙 트리에 삽입하기 위한 의사 코드입니다.

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();
}

위의 코드는 red-black 트리를 만들고 삽입, 삭제 및 회전 작업을 적용합니다.

출력:

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.

LinkedIn Facebook

C++의 레드 블랙 트리

Red-Black 트리에서 하위 트리의 회전

삽입

삭제

관련 문장 - C++ Tree