Python中的红黑树介绍

2023-04-11 00:00:00 python 红黑 介绍

红黑树（Red-Black Tree），是一种自平衡二叉查找树。在红黑树中，每个结点要么是红色的，要么是黑色的。

红黑树的特点：

  1. 每个节点不是红色就是黑色；

  2. 根节点是黑色的；

  3. 叶子节点（NIL节点，不包含任何数据）是黑色的；

  4. 如果一个节点是红色的，则它的两个子节点都是黑色的；

  5. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点。

红黑树的定义已经讲了，下面来说说它的性质。

红黑树的性质：

  1. 每个结点要么是红色，要么是黑色；

  2. 根结点是黑色的；

  3. 如果一个结点是红色的，那么它的子结点必须是黑色的；

  4. 对于每个结点，从该结点到叶子结点的每条路径上包含的黑色结点数都相同；

  5. 空结点（NIL结点）是黑色的。

下面是Python代码实现红黑树：

RED = True
BLACK = False

class Node:
    def __init__(self, key, value, color=RED):
        self.key = key
        self.value = value
        self.left, self.right = None, None
        self.color = color

class RedBlackTree:
    def __init__(self):
        self.root = None

    def is_red(self, node):
        return node is not None and node.color == RED

    def left_rotate(self, node):
        x = node.right
        node.right = x.left
        x.left = node
        x.color = node.color
        node.color = RED
        return x

    def right_rotate(self, node):
        x = node.left
        node.left = x.right
        x.right = node
        x.color = node.color
        node.color = RED
        return x

    def flip_color(self, node):
        node.color = RED
        node.left.color = BLACK
        node.right.color = BLACK

    def put(self, key, value):
        def _put(node, key, value):
            if node is None:
                return Node(key, value)

            if key < node.key:
                node.left = _put(node.left, key, value)
            elif key > node.key:
                node.right = _put(node.right, key, value)
            else:
                node.value = value

            if self.is_red(node.right) and not self.is_red(node.left):
                node = self.left_rotate(node)
            if self.is_red(node.left) and self.is_red(node.left.left):
                node = self.right_rotate(node)
            if self.is_red(node.left) and self.is_red(node.right):
                self.flip_color(node)

            return node

        self.root = _put(self.root, key, value)
        self.root.color = BLACK

    def get(self, key):
        node = self.root
        while node:
            if key < node.key:
                node = node.left
            elif key > node.key:
                node = node.right
            else:
                return node.value



if __name__ == '__main__':
    t = RedBlackTree()
    t.put('p', 'pidancode.com')
    t.put('e', '皮蛋编程')
    t.put('c', 'Coding')
    t.put('o', 'Object')
    t.put('r', 'Red-black')
    t.put('d', 'Data')
    print(t.get('p'))
    print(t.get('e'))
    print(t.get('c'))
    print(t.get('o'))
    print(t.get('r'))
    print(t.get('d'))

输出结果：

pidancode.com

皮蛋编程

Coding

Object

Red-black

Data

这就是红黑树的完整实现和代码演示。

相关文章