C++ 中的红黑树

当前位置：主页 > 学无止境 > 编程语言 > C++ >

Python PHP Java Go TypeScript C++ Vba Node.js C语言 MATLAB

C++ 中的红黑树

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

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

C++ 中的红黑树

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

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

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

红黑树

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

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

红黑树中子树的旋转

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

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

插入

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

使用普通 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();
}

上面的代码将创建一棵红黑树并应用插入、删除和旋转操作。

输出：

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++ 下载文件

下一篇：没有了

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

本文地址：

用 C++ 下载文件

发布时间：2023/08/27 浏览次数：198 分类：C++

本文介绍如何使用 C++ 下载文件。用 C++ 下载文件使用 C++ 下载文件是一项简单的操作，可以使用 win32 API URLDownloadToFile 来完成。

C++ 函数末尾的常量

发布时间：2023/08/27 浏览次数：197 分类：C++

本文介绍在 C++ 函数末尾使用 const 关键字。C++ 函数末尾的 const 关键字 const 成员函数是一旦声明就不再更改或修改的函数。

C++ 模板多种类型

发布时间：2023/08/27 浏览次数：72 分类：C++

本文介绍了 C++ 中多类型模板的使用。C++ 模板多种类型 C++ 中的模板可以定义为创建通用函数和类的公式蓝图。

C++ 类中的辅助函数

发布时间：2023/08/27 浏览次数：73 分类：C++

本文介绍如何在 C++ 类中实现辅助函数。类中的 C++ 辅助函数辅助函数是一种不由最终用户实例化的函数，但提供在另一个类内部使用的有用功能。

C++ 中的结构体继承

发布时间：2023/08/27 浏览次数：84 分类：C++

结构体和类很相似，但不同之处在于它们对面向对象编程中其他类或函数的可访问性。默认情况下，结构被指定为公共的，而类是私有的。并且在继承中，我们不能继承私有指定的类；我们必

C++ 中 Struct 和 Typedef Struct 的区别

发布时间：2023/08/27 浏览次数：94 分类：C++

This is a brief article about the difference between struct and typedef struct in C++.这篇小文章将讨论 C++ 中的关键字 typedef。我们还将讨论 C++ 中简单结构和 typedef 结构之间的区别。C/C++ 中的 typedef 关键字 type

C++ 结构体默认值初始化

发布时间：2023/08/26 浏览次数：200 分类：C++

本文将介绍如何在 C++ 中初始化结构体中的默认值。在 C++ 中初始化结构中的默认值初始化默认值主要有两种方法；第一个是使用构造函数，第二个是不使用构造函数。

C++ 匿名结构体

发布时间：2023/08/26 浏览次数：159 分类：C++

本文介绍了 C++ 中匿名结构的使用。C++ 中的匿名结构体 C++ 不支持匿名结构体，因为 C 语言也不支持匿名结构，但与 C 不同，C++ 确实支持匿名联合。

在 C++ 中实现具有多个条件的 if 语句

发布时间：2023/08/26 浏览次数：185 分类：C++

C++ 逻辑运算符 && 或 || 可在 if 语句中使用以同时检查多个条件。本文将详细讨论如何在 C++ 中使用具有多个条件的 if 语句，并结合相关示例。

迹忆客专注技术分享

C++ 中的红黑树

C++ 中的红黑树

红黑树中子树的旋转

插入

删除

相关文章

用 C++ 下载文件

C++ 函数末尾的常量

C++ 模板多种类型

C++ 类中的辅助函数

C++ 中的结构体继承

C++ 中 Struct 和 Typedef Struct 的区别

C++ 结构体默认值初始化

C++ 匿名结构体

在 C++ 中实现具有多个条件的 if 语句

扫一扫阅读全部技术教程

社交账号

 https://www.github.com/onmpw

 qq:1244347461



最新推荐

教程更新

热门标签

C++ 中的红黑树

C++ 中的红黑树

红黑树中子树的旋转

插入

删除

相关文章

扫一扫阅读全部技术教程

社交账号  https://www.github.com/onmpw  qq:1244347461 

最新推荐

教程更新

热门标签

社交账号

 https://www.github.com/onmpw

 qq:1244347461

