迹忆客 专注技术分享

当前位置：主页 > 学无止境 > 编程语言 > C++ >
Python PHP Java Go TypeScript C++ Vba Node.js C语言 MATLAB

C++ 中的红黑树

作者：迹忆客 最近更新：2023/08/26 浏览次数：

本文介绍了 C++ 中的红黑树。

C++ 中的红黑树

红黑树被认为是一种自平衡二叉搜索树，其中每个节点都包含表示节点颜色的不同属性。 红黑具有以下五个属性。

  1. 红/黑属性 - 树中的每个节点都有颜色，红色或黑色。
  2. 根属性 - 根始终是黑色的。
  3. 叶子属性 - 每片叶子 (NIL) 始终是黑色的。
  4. 红色属性 - 所有红色节点子节点都必须是黑色（如果有）。
  5. 深度属性 - 从一个节点到另一后代叶子的任何路径都将具有与黑色节点数相同的黑色深度平均值。

如果任何地方都不满足上述条件，那么该树就不可能是红黑树。 红黑树的结构见下图。

红黑树

正如我们所看到的，每个节点都有一个颜色、键、左子节点、右子节点和除根节点之外的父节点。

从以上性质来看，红黑树应该是自平衡树，因为节点颜色的限制保证了从根到前导的任何路径的长度不超过两倍，这有助于树保持 平衡自身。

红黑树中子树的旋转

在旋转过程中，子树节点的位置会互换，这用于在红黑树受到插入和删除等其他操作影响时保持红黑树的属性。 旋转的类型有：

  1. 左旋转 - 在这种类型的旋转中，右侧节点的排列将转换为左侧节点的排列。
  2. 右旋转 - 在这种类型的旋转中，左侧节点的排列将转换为右侧节点的排列。
  3. 左右旋转 - 在这种类型的旋转中，排列将首先向左移动，然后向右移动。
  4. 右左旋转 - 在这种类型的旋转中，排列将首先向右移动，然后向左移动。
  5. 重新着色 - 在重新着色中，我们翻转节点的颜色； 例如，如果一个节点是红色的，它就会变成黑色，反之亦然。

插入

按照以下步骤将节点插入红黑树中。

  1. 使用普通 BST 操作插入节点。
  2. 将插入的节点着色为红色。
  3. 最后检查插入是否违反红黑树性质； 如果确实如此，我们必须修复它。

这是在红黑树中插入的伪代码。

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)

上一篇：用 C++ 下载文件

下一篇：用 C++ 构建解析树

转载请发邮件至 1244347461@qq.com 进行申请，经作者同意之后，转载请以链接形式注明出处

本文地址：

相关文章

Arduino 中停止循环

发布时间：2024/03/13 浏览次数：444 分类：C++

可以使用 exit(0)，无限循环和 Sleep_n0m1 库在 Arduino 中停止循环。

Arduino 复位

发布时间：2024/03/13 浏览次数：315 分类：C++

可以通过使用复位按钮，Softwarereset 库和 Adafruit SleepyDog 库来复位 Arduino。

Arduino 的字符转换为整型

发布时间：2024/03/13 浏览次数：181 分类：C++

可以使用简单的方法 toInt()函数和 Serial.parseInt()函数将 char 转换为 int。

Arduino 串口打印多个变量

发布时间：2024/03/13 浏览次数：381 分类：C++

可以使用 Serial.print()和 Serial.println()函数在串口监视器上显示变量值。

Arduino if 语句

发布时间：2024/03/13 浏览次数：123 分类：C++

可以使用 if 语句检查 Arduino 中的不同条件。

Arduino ICSP

发布时间：2024/03/13 浏览次数：214 分类：C++

ICSP 引脚用于两个 Arduino 之间的通信以及对 Arduino 引导加载程序进行编程。

使用 C++ 编程 Arduino

发布时间：2024/03/13 浏览次数：127 分类：C++

本教程将讨论使用 Arduino IDE 在 C++ 中对 Arduino 进行编程。

Arduino 中的子程序

发布时间：2024/03/13 浏览次数：168 分类：C++

可以通过在 Arduino 中声明函数来处理子程序。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

Js Javascript Prototype Vue WEB Python Pandas Mysql Jquery Angular Flask Django CSharp C# Batch Linux Bash C++ arduino Numpy powershell R Rust Ruby
扫码一下
查看教程更方便