红黑树

Table of content
上一页
下一页

红黑树是另一种平衡二叉搜索树，具有两种颜色的节点：红色和黑色。它是一种自平衡二叉搜索树，利用这些颜色在插入和删除操作期间保持平衡因子。因此，在红黑树操作期间，内存使用1位存储来容纳每个节点的颜色信息。

在红黑树（也称为RB树）中，为节点分配颜色时需要遵循不同的条件。

  • 根节点始终为黑色。

  • 不允许出现两个相邻的红色节点。

  • 树中的每条路径（从根节点到叶节点）必须具有相同数量的黑色节点。

尽管AVL树比RB树更平衡，AVL树的平衡算法比RB树更严格，但通过RB树可以使多个和更快的插入和删除操作更高效。

RB trees

图：RB树

红黑树的基本操作

红黑树的操作包括通常在二叉搜索树上执行的所有基本操作。RB树的一些基本操作包括：

  • 插入

  • 删除

  • 搜索

插入操作

红黑树的插入操作遵循二叉搜索树相同的插入算法。元素按照二叉搜索属性插入，此外，节点被着色为红色和黑色以根据红黑树属性平衡树。

按照以下步骤，通过保持二叉搜索树和红黑树属性来将元素插入红黑树。

情况1 - 检查树是否为空；如果为空，则将当前节点设为根节点并将其颜色设置为黑色。

情况2 - 但如果树不为空，我们创建一个新节点并将其颜色设置为红色。这里我们面临两种不同的情况：

  • 如果新节点的父节点是黑色，则我们退出操作，树保持不变。

  • 如果新节点的父节点是红色，并且父节点的兄弟节点的颜色是黑色或不存在，则我们应用适当的旋转并相应地重新着色。

  • 如果新节点的父节点是红色，并且父节点的兄弟节点是红色，则将父节点、兄弟节点和祖父节点重新着色为黑色。只有当祖父节点不是根节点时才重新着色祖父节点；如果它是根节点，则只重新着色父节点和兄弟节点。

示例

让我们为前7个整数构造一个RB树，以便详细了解插入操作：

检查树为空，因此添加的第一个节点是根节点，颜色为黑色。

first node

现在，树不为空，因此我们创建一个新节点并添加下一个整数，颜色为红色。

new node

节点不违反二叉搜索树和RB树属性，因此我们继续添加另一个节点。

树不为空；我们创建一个新的红色节点，并将下一个整数添加到其中。但是新节点的父节点不是黑色。

third node

目前的树违反了二叉搜索树和RB树属性；由于父节点的兄弟节点为NULL，我们应用适当的旋转并重新着色节点。

suitable rotation

现在RB树属性已恢复，我们向树中添加另一个节点：

RB Tree property

树再次违反了RB树的平衡属性，因此我们检查父节点的兄弟节点颜色，在本例中为红色，因此我们只需重新着色父节点和兄弟节点。

RB Tree balance property

接下来我们插入元素5，这使得树再次违反RB树的平衡属性。

insert element 5

由于兄弟节点为NULL，我们应用适当的旋转和重新着色。

sibling is NULL

现在，我们插入元素6，但是RB树属性被违反，需要应用一个插入情况：

insert element 6

父节点的兄弟节点是红色，因此我们重新着色父节点、父节点的兄弟节点和祖父节点，因为祖父节点不是根节点。

recolor parent

现在，我们添加最后一个元素7，但新节点的父节点是红色。

add last element

由于父节点的兄弟节点为NULL，我们应用适当的旋转（RR旋转）

RB Tree achieved

最终得到RB树。

删除操作

红黑树的删除操作必须以这样一种方式执行：它必须恢复二叉搜索树和红黑树的所有属性。按照以下步骤在红黑树上执行删除操作：

首先，我们根据二叉搜索树属性执行删除。

情况1 - 如果要删除的节点或节点的父节点是红色，则只需删除它。

情况2 - 如果节点是双黑，则只需删除双黑（当要删除的节点是黑色叶节点时，就会出现双黑，因为它还会累加被认为是黑色的NULL节点）。

情况3 - 如果双黑节点的兄弟节点也是黑色节点，并且其子节点也是黑色，则执行以下步骤：

  • 删除双黑

  • 将其父节点重新着色为黑色（如果父节点是红色，则变为黑色；如果父节点已经是黑色，则变为双黑）

  • 将父节点的兄弟节点重新着色为红色

  • 如果仍然存在双黑节点，我们应用其他情况。

情况4 - 如果双黑节点的兄弟节点是红色，我们执行以下步骤：

  • 交换父节点和父节点的兄弟节点的颜色。

  • 朝双黑节点的方向旋转父节点

  • 重新应用其他适用情况。

情况5 - 如果双黑节点的兄弟节点是黑色节点，但最靠近双黑的兄弟节点的子节点是红色，则执行以下步骤：

  • 交换双黑节点的兄弟节点和相关兄弟节点子节点的颜色

  • 朝与双黑节点相反的方向旋转兄弟节点（即，如果双黑节点是右子节点，则应用左旋转，反之亦然）

  • 应用情况6。

情况6 - 如果双黑节点的兄弟节点是黑色节点，但离双黑节点较远的兄弟节点的子节点是红色，则执行以下步骤：

  • 交换双黑节点的父节点和兄弟节点的颜色

  • 朝双黑节点的方向旋转父节点（即，如果双黑节点是右子节点，则应用右旋转，反之亦然）

  • 删除双黑

  • 将红色子节点的颜色更改为黑色。

示例

考虑上面构造的相同的红黑树，让我们从树中删除一些元素。

RB Tree achieved

从树中删除元素4、5、3。

要删除元素4，让我们首先执行二叉搜索删除。

delete element 4

执行二叉搜索删除后，RB树属性没有被破坏，因此树保持不变。

然后，我们使用二叉搜索删除来删除元素5

delete element 5

但是执行二叉搜索删除后，RB属性被破坏，即树中所有路径不包含相同数量的黑色节点；因此，我们交换颜色以平衡树。

RB property violated

然后，我们从获得的树中删除节点3：

应用二叉搜索删除，我们正常删除节点3，因为它是一个叶节点。并且我们得到一个双节点，因为3是一个黑色节点。

delete node 3

我们应用情况3删除，因为双黑节点的兄弟节点是黑色，其子节点也是黑色。在这里，我们删除双黑，重新着色双黑节点的父节点和兄弟节点。

RB Tree property maintained

所有所需节点都被删除，并且保持了RB树属性。

红黑树的搜索操作与二叉搜索树的算法相同。它遍历树，并将每个节点与要搜索的关键元素进行比较；如果找到，则返回成功搜索；否则，返回不成功搜索。

完整实现

以下是各种编程语言中红黑树的完整实现：

C++ Java Python
// C++ program for Red black trees algorithmn
#include <iostream>
using namespace std;
struct Node {
  int data;
  Node *parent;
  Node *left;
  Node *right;
  int color;
};
typedef Node *NodePtr;
class RedBlackTree {
   private:
  NodePtr root;
  NodePtr TNULL;
  void initializeNULLNode(NodePtr node, NodePtr parent) {
    node->data = 0;
    node->parent = parent;
    node->left = nullptr;
    node->right = nullptr;
    node->color = 0;
  }
  // Preorder
  void preOrderHelper(NodePtr node) {
    if (node != TNULL) {
      cout << node->data << " ";
      preOrderHelper(node->left);
      preOrderHelper(node->right);
    }
  }
  // Inorder
  void inOrderHelper(NodePtr node) {
    if (node != TNULL) {
      inOrderHelper(node->left);
      cout << node->data << " ";
      inOrderHelper(node->right);
    }
  }
  // Post order
  void postOrderHelper(NodePtr node) {
    if (node != TNULL) {
      postOrderHelper(node->left);
      postOrderHelper(node->right);
      cout << node->data << " ";
    }
  }
  NodePtr searchTreeHelper(NodePtr node, int key) {
    if (node == TNULL || key == node->data) {
      return node;
    }
    if (key < node->data) {
      return searchTreeHelper(node->left, key);
    }
    return searchTreeHelper(node->right, key);
  }
  // For balancing the tree after deletion
  void deleteFix(NodePtr x) {
    NodePtr s;
    while (x != root && x->color == 0) {
      if (x == x->parent->left) {
        s = x->parent->right;
        if (s->color == 1) {
          s->color = 0;
          x->parent->color = 1;
          leftRotate(x->parent);
          s = x->parent->right;
        }
        if (s->left->color == 0 && s->right->color == 0) {
          s->color = 1;
          x = x->parent;
        } else {
          if (s->right->color == 0) {
            s->left->color = 0;
            s->color = 1;
            rightRotate(s);
            s = x->parent->right;
          }
          s->color = x->parent->color;
          x->parent->color = 0;
          s->right->color = 0;
          leftRotate(x->parent);
          x = root;
        }
      } else {
        s = x->parent->left;
        if (s->color == 1) {
          s->color = 0;
          x->parent->color = 1;
          rightRotate(x->parent);
          s = x->parent->left;
        }
        if (s->right->color == 0 && s->right->color == 0) {
          s->color = 1;
          x = x->parent;
        } else {
          if (s->left->color == 0) {
            s->right->color = 0;
            s->color = 1;
            leftRotate(s);
            s = x->parent->left;
          }
          s->color = x->parent->color;
          x->parent->color = 0;
          s->left->color = 0;
          rightRotate(x->parent);
          x = root;
        }
      }
    }
    x->color = 0;
  }
  void rbTransplant(NodePtr u, NodePtr v) {
    if (u->parent == nullptr) {
      root = v;
    } else if (u == u->parent->left) {
      u->parent->left = v;
    } else {
      u->parent->right = v;
    }
    v->parent = u->parent;
  }
  void deleteNodeHelper(NodePtr node, int key) {
    NodePtr z = TNULL;
    NodePtr x, y;
    while (node != TNULL) {
      if (node->data == key) {
        z = node;
      }
      if (node->data <= key) {
        node = node->right;
      } else {
        node = node->left;
      }
    }
    if (z == TNULL) {
      cout << "Key not found in the tree" << endl;
      return;
    }
    y = z;
    int y_original_color = y->color;
    if (z->left == TNULL) {
      x = z->right;
      rbTransplant(z, z->right);
    } else if (z->right == TNULL) {
      x = z->left;
      rbTransplant(z, z->left);
    } else {
      y = minimum(z->right);
      y_original_color = y->color;
      x = y->right;
      if (y->parent == z) {
        x->parent = y;
      } else {
        rbTransplant(y, y->right);
        y->right = z->right;
        y->right->parent = y;
      }
      rbTransplant(z, y);
      y->left = z->left;
      y->left->parent = y;
      y->color = z->color;
    }
    delete z;
    if (y_original_color == 0) {
      deleteFix(x);
    }
  }
  // For balancing the tree after insertion
  void insertFix(NodePtr k) {
    NodePtr u;
    while (k->parent->color == 1) {
      if (k->parent == k->parent->parent->right) {
        u = k->parent->parent->left;
        if (u->color == 1) {
          u->color = 0;
          k->parent->color = 0;
          k->parent->parent->color = 1;
          k = k->parent->parent;
        } else {
          if (k == k->parent->left) {
            k = k->parent;
            rightRotate(k);
          }
          k->parent->color = 0;
          k->parent->parent->color = 1;
          leftRotate(k->parent->parent);
        }
      } else {
        u = k->parent->parent->right;
        if (u->color == 1) {
          u->color = 0;
          k->parent->color = 0;
          k->parent->parent->color = 1;
          k = k->parent->parent;
        } else {
          if (k == k->parent->right) {
            k = k->parent;
            leftRotate(k);
          }
          k->parent->color = 0;
          k->parent->parent->color = 1;
          rightRotate(k->parent->parent);
        }
      }
      if (k == root) {
        break;
      }
    }
    root->color = 0;
  }
  void printHelper(NodePtr root, string indent, bool last) {
    if (root != TNULL) {
      cout << indent;
      if (last) {
        cout << "R----";
        indent += "   ";
      } else {
        cout << "L----";
        indent += "|  ";
      }
      string sColor = root->color ? "RED" : "BLACK";
      cout << root->data << "(" << sColor << ")" << endl;
      printHelper(root->left, indent, false);
      printHelper(root->right, indent, true);
    }
  }
   public:
  RedBlackTree() {
    TNULL = new Node;
    TNULL->color = 0;
    TNULL->left = nullptr;
    TNULL->right = 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->left != TNULL) {
      node = node->left;
    }
    return node;
  }
  NodePtr maximum(NodePtr node) {
    while (node->right != TNULL) {
      node = node->right;
    }
    return node;
  }
  NodePtr successor(NodePtr x) {
    if (x->right != TNULL) {
      return minimum(x->right);
    }
    NodePtr y = x->parent;
    while (y != TNULL && x == y->right) {
      x = y;
      y = y->parent;
    }
    return y;
  }
  NodePtr predecessor(NodePtr x) {
    if (x->left != TNULL) {
      return maximum(x->left);
    }
    NodePtr y = x->parent;
    while (y != TNULL && x == y->left) {
      x = y;
      y = y->parent;
    }
    return y;
  }
  void leftRotate(NodePtr x) {
    NodePtr y = x->right;
    x->right = y->left;
    if (y->left != TNULL) {
      y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
      this->root = y;
    } else if (x == x->parent->left) {
      x->parent->left = y;
    } else {
      x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
  }
  void rightRotate(NodePtr x) {
    NodePtr y = x->left;
    x->left = y->right;
    if (y->right != TNULL) {
      y->right->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
      this->root = y;
    } else if (x == x->parent->right) {
      x->parent->right = y;
    } else {
      x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
  }
  // Inserting a node
  void insert(int key) {
    NodePtr node = new Node;
    node->parent = nullptr;
    node->data = key;
    node->left = TNULL;
    node->right = TNULL;
    node->color = 1;
    NodePtr y = nullptr;
    NodePtr x = this->root;
    while (x != TNULL) {
      y = x;
      if (node->data < x->data) {
        x = x->left;
      } else {
        x = x->right;
      }
    }
    node->parent = y;
    if (y == nullptr) {
      root = node;
    } else if (node->data < y->data) {
      y->left = node;
    } else {
      y->right = node;
    }
    if (node->parent == nullptr) {
      node->color = 0;
      return;
    }
    if (node->parent->parent == nullptr) {
      return;
    }
    insertFix(node);
  }
  NodePtr getRoot() {
    return this->root;
  }
  void deleteNode(int data) {
    deleteNodeHelper(this->root, data);
  }
  void printTree() {
    if (root) {
      printHelper(this->root, "", true);
    }
  }
};
int main() {
  RedBlackTree V;
    V.insert(24);
    V.insert(33);
    V.insert(42);
    V.insert(51);
    V.insert(60);
    V.insert(40);
    V.insert(22);
  V.printTree();
  cout << endl
     << "After deleting an element" << endl;
  V.deleteNode(40);
  V.printTree();
}

输出

R----33(BLACK)
   L----24(BLACK)
   |  L----22(RED)
   R----51(RED)
      L----42(BLACK)
      |  L----40(RED)
      R----60(BLACK)

After deleting an element
R----33(BLACK)
   L----24(BLACK)
   |  L----22(RED)
   R----51(RED)
      L----42(BLACK)
      R----60(BLACK)

// Implementing Red-Black Tree in Java
class Node {
    int data;
    Node parent;
    Node left;
    Node right;
    int color;
}
public class RedBlackTree {
    private Node root;
    private Node TNULL;

    // Preorder
    private void preOrderHelper(Node node) {
        if (node != TNULL) {
            System.out.print(node.data + " ");
            preOrderHelper(node.left);
            preOrderHelper(node.right);
        }
    }
    // Inorder
    private void inOrderHelper(Node node) {
        if (node != TNULL) {
            inOrderHelper(node.left);
            System.out.print(node.data + " ");
            inOrderHelper(node.right);
        }
    }

    // Post order
    private void postOrderHelper(Node node) {
        if (node != TNULL) {
            postOrderHelper(node.left);
            postOrderHelper(node.right);
            System.out.print(node.data + " ");
        }
    }

    // Search the tree
    private Node searchTreeHelper(Node node, int key) {
        if (node == TNULL || key == node.data) {
            return node;
        }

        if (key < node.data) {
            return searchTreeHelper(node.left, key);
        }
        return searchTreeHelper(node.right, key);
    }

    // Balance the tree after deletion of a node
    private void fixDelete(Node x) {
        Node s;
        while (x != root && x.color == 0) {
            if (x == x.parent.left) {
                s = x.parent.right;
                if (s.color == 1) {
                    s.color = 0;
                    x.parent.color = 1;
                    leftRotate(x.parent);
                    s = x.parent.right;
                }

                if (s.left.color == 0 && s.right.color == 0) {
                    s.color = 1;
                    x = x.parent;
                } else {
                    if (s.right.color == 0) {
                        s.left.color = 0;
                        s.color = 1;
                        rightRotate(s);
                        s = x.parent.right;
                    }

                    s.color = x.parent.color;
                    x.parent.color = 0;
                    s.right.color = 0;
                    leftRotate(x.parent);
                    x = root;
                }
            } else {
                s = x.parent.left;
                if (s.color == 1) {
                    s.color = 0;
                    x.parent.color = 1;
                    rightRotate(x.parent);
                    s = x.parent.left;
                }

                if (s.right.color == 0 && s.right.color == 0) {
                    s.color = 1;
                    x = x.parent;
                } else {
                    if (s.left.color == 0) {
                        s.right.color = 0;
                        s.color = 1;
                        leftRotate(s);
                        s = x.parent.left;
                    }

                    s.color = x.parent.color;
                    x.parent.color = 0;
                    s.left.color = 0;
                    rightRotate(x.parent);
                    x = root;
                }
            }
        }
        x.color = 0;
    }

    private void rbTransplant(Node u, Node v) {
        if (u.parent == null) {
            root = v;
        } else if (u == u.parent.left) {
            u.parent.left = v;
        } else {
            u.parent.right = v;
        }
        v.parent = u.parent;
    }

    private void deleteNodeHelper(Node node, int key) {
        Node z = TNULL;
        Node x, y;
        while (node != TNULL) {
            if (node.data == key) {
                z = node;
            }

            if (node.data <= key) {
                node = node.right;
            } else {
                node = node.left;
            }
        }

        if (z == TNULL) {
            System.out.println("Couldn't find key in the tree");
            return;
        }

        y = z;
        int yOriginalColor = y.color;
        if (z.left == TNULL) {
            x = z.right;
            rbTransplant(z, z.right);
        } else if (z.right == TNULL) {
            x = z.left;
            rbTransplant(z, z.left);
        } else {
            y = minimum(z.right);
            yOriginalColor = y.color;
            x = y.right;
            if (y.parent == z) {
                x.parent = y;
            } else {
                rbTransplant(y, y.right);
                y.right = z.right;
                y.right.parent = y;
            }

            rbTransplant(z, y);
            y.left = z.left;
            y.left.parent = y;
            y.color = z.color;
        }
        if (yOriginalColor == 0) {
            fixDelete(x);
        }
    }

    // Balance the node after insertion
    private void fixInsert(Node k) {
        Node u;
        while (k.parent.color == 1) {
            if (k.parent == k.parent.parent.right) {
                u = k.parent.parent.left;
                if (u.color == 1) {
                    u.color = 0;
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        k = k.parent;
                        rightRotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    leftRotate(k.parent.parent);
                }
            } else {
                u = k.parent.parent.right;

                if (u.color == 1) {
                    u.color = 0;
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.right) {
                        k = k.parent;
                        leftRotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    rightRotate(k.parent.parent);
                }
            }
            if (k == root) {
                break;
            }
        }
        root.color = 0;
    }

    private void printHelper(Node root, String indent, boolean last) {
        if (root != TNULL) {
            System.out.print(indent);
            if (last) {
                System.out.print("R----");
                indent += "   ";
            } else {
                System.out.print("L----");
                indent += "|  ";
            }

            String sColor = root.color == 1 ? "RED" : "BLACK";
            System.out.println(root.data + "(" + sColor + ")");
            printHelper(root.left, indent, false);
            printHelper(root.right, indent, true);
        }
    }

    public RedBlackTree() {
        TNULL = new Node();
        TNULL.color = 0;
        TNULL.left = null;
        TNULL.right = null;
        root = TNULL;
    }

    public void preorder() {
        preOrderHelper(this.root);
    }

    public void inorder() {
        inOrderHelper(this.root);
    }

    public void postorder() {
        postOrderHelper(this.root);
    }

    public Node searchTree(int k) {
        return searchTreeHelper(this.root, k);
    }

    public Node minimum(Node node) {
        while (node.left != TNULL) {
            node = node.left;
        }
        return node;
    }

    public Node maximum(Node node) {
        while (node.right != TNULL) {
            node = node.right;
        }
        return node;
    }

    public Node successor(Node x) {
        if (x.right != TNULL) {
            return minimum(x.right);
        }

        Node y = x.parent;
        while (y != TNULL && x == y.right) {
            x = y;
            y = y.parent;
        }
        return y;
    }

    public Node predecessor(Node x) {
        if (x.left != TNULL) {
            return maximum(x.left);
        }

        Node y = x.parent;
        while (y != TNULL && x == y.left) {
            x = y;
            y = y.parent;
        }

        return y;
    }

    public void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != TNULL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    public void rightRotate(Node x) {
        Node y = x.left;
        x.left = y.right;
        if (y.right != TNULL) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    public void insert(int key) {
        Node node = new Node();
        node.parent = null;
        node.data = key;
        node.left = TNULL;
        node.right = TNULL;
        node.color = 1;

        Node y = null;
        Node x = this.root;

        while (x != TNULL) {
            y = x;
            if (node.data < x.data) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y == null) {
            root = node;
        } else if (node.data < y.data) {
            y.left = node;
        } else {
            y.right = node;
        }

        if (node.parent == null) {
            node.color = 0;
            return;
        }

        if (node.parent.parent == null) {
            return;
        }

        fixInsert(node);
    }

    public Node getRoot() {
        return this.root;
    }

    public void deleteNode(int data) {
        deleteNodeHelper(this.root, data);
    }

    public void printTree() {
        printHelper(this.root, "", true);
    }

    public static void main(String[] args) {
        RedBlackTree V = new RedBlackTree();
        V.insert(24);
        V.insert(33);
        V.insert(42);
        V.insert(51);
        V.insert(60);
        V.insert(40);
        V.insert(22);
        V.printTree();

        System.out.println("\nAfter deleting an element:");
        V.deleteNode(40);
        V.printTree();
    }
}

输出

R----33(BLACK)
   L----24(BLACK)
   |  L----22(RED)
R----51(RED)
L----42(BLACK)
|  L----40(RED)
      R----60(BLACK)
After deleting an element:
R----33(BLACK)
L----24(BLACK)
   |  L----22(RED)
R----51(RED)
L----42(BLACK)
R----60(BLACK)

#python program for Red black trees
import sys
# Node creation
class Node():
    def __init__(self, item):
        self.item = item
        self.parent = None
        self.left = None
        self.right = None
        self.color = 1
class RedBlackTree():
    def __init__(self):
        self.TNULL = Node(0)
        self.TNULL.color = 0
        self.TNULL.left = None
        self.TNULL.right = None
        self.root = self.TNULL
    # Preorder
    def pre_order_helper(self, node):
        if node != TNULL:
            sys.stdout.write(node.item + " ")
            self.pre_order_helper(node.left)
            self.pre_order_helper(node.right)
    # Inorder
    def in_order_helper(self, node):
        if node != TNULL:
            self.in_order_helper(node.left)
            sys.stdout.write(node.item + " ")
            self.in_order_helper(node.right)
    # Postorder
    def post_order_helper(self, node):
        if node != TNULL:
            self.post_order_helper(node.left)
            self.post_order_helper(node.right)
            sys.stdout.write(node.item + " ")
    # Search the tree
    def search_tree_helper(self, node, key):
        if node == TNULL or key == node.item:
            return node
        if key < node.item:
            return self.search_tree_helper(node.left, key)
        return self.search_tree_helper(node.right, key)
    # Balancing the tree after deletion
    def delete_fix(self, x):
        while x != self.root and x.color == 0:
            if x == x.parent.left:
                s = x.parent.right
                if s.color == 1:
                    s.color = 0
                    x.parent.color = 1
                    self.left_rotate(x.parent)
                    s = x.parent.right
                if s.left.color == 0 and s.right.color == 0:
                    s.color = 1
                    x = x.parent
                else:
                    if s.right.color == 0:
                        s.left.color = 0
                        s.color = 1
                        self.right_rotate(s)
                        s = x.parent.right
                    s.color = x.parent.color
                    x.parent.color = 0
                    s.right.color = 0
                    self.left_rotate(x.parent)
                    x = self.root
            else:
                s = x.parent.left
                if s.color == 1:
                    s.color = 0
                    x.parent.color = 1
                    self.right_rotate(x.parent)
                    s = x.parent.left

                if s.right.color == 0 and s.right.color == 0:
                    s.color = 1
                    x = x.parent
                else:
                    if s.left.color == 0:
                        s.right.color = 0
                        s.color = 1
                        self.left_rotate(s)
                        s = x.parent.left
                    s.color = x.parent.color
                    x.parent.color = 0
                    s.left.color = 0
                    self.right_rotate(x.parent)
                    x = self.root
        x.color = 0
    def __rb_transplant(self, u, v):
        if u.parent == None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        v.parent = u.parent
    # Node deletion
    def delete_node_helper(self, node, key):
        z = self.TNULL
        while node != self.TNULL:
            if node.item == key:
                z = node
            if node.item <= key:
                node = node.right
            else:
                node = node.left
        if z == self.TNULL:
            print("Cannot find key in the tree")
            return
        y = z
        y_original_color = y.color
        if z.left == self.TNULL:
            x = z.right
            self.__rb_transplant(z, z.right)
        elif (z.right == self.TNULL):
            x = z.left
            self.__rb_transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            y_original_color = y.color
            x = y.right
            if y.parent == z:
                x.parent = y
            else:
                self.__rb_transplant(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.__rb_transplant(z, y)
            y.left = z.left
            y.left.parent = y
            y.color = z.color
        if y_original_color == 0:
            self.delete_fix(x)
    # Balance the tree after insertion
    def fix_insert(self, k):
        while k.parent.color == 1:
            if k.parent == k.parent.parent.right:
                u = k.parent.parent.left
                if u.color == 1:
                    u.color = 0
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    k = k.parent.parent
                else:
                    if k == k.parent.left:
                        k = k.parent
                        self.right_rotate(k)
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    self.left_rotate(k.parent.parent)
            else:
                u = k.parent.parent.right
                if u.color == 1:
                    u.color = 0
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    k = k.parent.parent
                else:
                    if k == k.parent.right:
                        k = k.parent
                        self.left_rotate(k)
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    self.right_rotate(k.parent.parent)
            if k == self.root:
                break
        self.root.color = 0
    # Printing the tree
    def __print_helper(self, node, indent, last):
        if node != self.TNULL:
            sys.stdout.write(indent)
            if last:
                sys.stdout.write("R----")
                indent += "     "
            else:
                sys.stdout.write("L----")
                indent += "|    "
            s_color = "RED" if node.color == 1 else "BLACK"
            print(str(node.item) + "(" + s_color + ")")
            self.__print_helper(node.left, indent, False)
            self.__print_helper(node.right, indent, True)
    def preorder(self):
        self.pre_order_helper(self.root)
    def inorder(self):
        self.in_order_helper(self.root)
    def postorder(self):
        self.post_order_helper(self.root)
    def searchTree(self, k):
        return self.search_tree_helper(self.root, k)
    def minimum(self, node):
        while node.left != self.TNULL:
            node = node.left
        return node
    def maximum(self, node):
        while node.right != self.TNULL:
            node = node.right
        return node
    def successor(self, x):
        if x.right != self.TNULL:
            return self.minimum(x.right)
        y = x.parent
        while y != self.TNULL and x == y.right:
            x = y
            y = y.parent
        return y
    def predecessor(self,  x):
        if (x.left != self.TNULL):
            return self.maximum(x.left)
        y = x.parent
        while y != self.TNULL and x == y.left:
            x = y
            y = y.parent
        return y
    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.TNULL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y
    def right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.TNULL:
            y.right.parent = x
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y
    def insert(self, key):
        node = Node(key)
        node.parent = None
        node.item = key
        node.left = self.TNULL
        node.right = self.TNULL
        node.color = 1
        y = None
        x = self.root
        while x != self.TNULL:
            y = x
            if node.item < x.item:
                x = x.left
            else:
                x = x.right
        node.parent = y
        if y == None:
            self.root = node
        elif node.item < y.item:
            y.left = node
        else:
            y.right = node
        if node.parent == None:
            node.color = 0
            return
        if node.parent.parent == None:
            return
        self.fix_insert(node)
    def get_root(self):
        return self.root
    def delete_node(self, item):
        self.delete_node_helper(self.root, item)
    def print_tree(self):
        self.__print_helper(self.root, "", True)
if __name__ == "__main__":
    V = RedBlackTree()
    V.insert(24)
    V.insert(33)
    V.insert(42)
    V.insert(51)
    V.insert(60)
    V.insert(40)
    V.insert(22)
    V.print_tree()
    print("\nAfter deleting an element")
    V.delete_node(40)
    V.print_tree()

输出

R----33(BLACK)
     L----24(BLACK)
     |    L----22(RED)
R----51(RED)
          L----42(BLACK)
          |    L----40(RED)
          R----60(BLACK)

After deleting an element
R----33(BLACK)
     L----24(BLACK)
     |    L----22(RED)
     R----51(RED)
          L----42(BLACK)
          R----60(BLACK)
打印页面
上一页
下一页
广告
© . All rights reserved.