红黑树代码 python

以下是一个Python实现的红黑树代码示例： ```python RED = 0 BLACK = 1 class Node: def __init__(self, key, value, color=RED): self.key = key self.value = value self.color = color self.left = None self.right = None self.parent = None class RedBlackTree: def __init__(self): self.root = None def insert(self, key, value): node = Node(key, value) if not self.root: self.root = node node.color = BLACK return parent = None cur = self.root while cur: parent = cur if key < cur.key: cur = cur.left else: cur = cur.right node.parent = parent if key < parent.key: parent.left = node else: parent.right = node self._insert_fixup(node) def _insert_fixup(self, node): while node.parent and node.parent.color == RED: if node.parent == node.parent.parent.left: uncle = node.parent.parent.right if uncle and uncle.color == RED: node.parent.color = BLACK uncle.color = BLACK node.parent.parent.color = RED node = node.parent.parent else: if node == node.parent.right: node = node.parent self._left_rotate(node) node.parent.color = BLACK node.parent.parent.color = RED self._right_rotate(node.parent.parent) else: uncle = node.parent.parent.left if uncle and uncle.color == RED: node.parent.color = BLACK uncle.color = BLACK node.parent.parent.color = RED node = node.parent.parent else: if node == node.parent.left: node = node.parent self._right_rotate(node) node.parent.color = BLACK node.parent.parent.color = RED self._left_rotate(node.parent.parent) self.root.color = BLACK def delete(self, key): node = self._search(key) if not node: return if node.left and node.right: succ = self._minimum(node.right) node.key, node.value = succ.key, succ.value node = succ child = node.left if node.left else node.right if child: child.parent = node.parent if not node.parent: self.root = child else: if node == node.parent.left: node.parent.left = child else: node.parent.right = child if node.color == BLACK: self._delete_fixup(child, node.parent) del node def _delete_fixup(self, node, parent): while node != self.root and (not node or node.color == BLACK): if node == parent.left: sibling = parent.right if sibling.color == RED: sibling.color = BLACK parent.color = RED self._left_rotate(parent) sibling = parent.right if (not sibling.left or sibling.left.color == BLACK) and \ (not sibling.right or sibling.right.color == BLACK): sibling.color = RED node = parent parent = node.parent else: if not sibling.right or sibling.right.color == BLACK: sibling.left.color = BLACK sibling.color = RED self._right_rotate(sibling) sibling = parent.right sibling.color = parent.color parent.color = BLACK sibling.right.color = BLACK self._left_rotate(parent) node = self.root else: sibling = parent.left if sibling.color == RED: sibling.color = BLACK parent.color = RED self._right_rotate(parent) sibling = parent.left if (not sibling.left or sibling.left.color == BLACK) and \ (not sibling.right or sibling.right.color == BLACK): sibling.color = RED node = parent parent = node.parent else: if not sibling.left or sibling.left.color == BLACK: sibling.right.color = BLACK sibling.color = RED self._left_rotate(sibling) sibling = parent.left sibling.color = parent.color parent.color = BLACK sibling.left.color = BLACK self._right_rotate(parent) node = self.root if node: node.color = BLACK def _search(self, key): cur = self.root while cur: if key == cur.key: return cur elif key < cur.key: cur = cur.left else: cur = cur.right return None def _minimum(self, node): while node.left: node = node.left return node def _left_rotate(self, node): right = node.right node.right = right.left if right.left: right.left.parent = node right.parent = node.parent if not node.parent: self.root = right else: if node == node.parent.left: node.parent.left = right else: node.parent.right = right right.left = node node.parent = right def _right_rotate(self, node): left = node.left node.left = left.right if left.right: left.right.parent = node left.parent = node.parent if not node.parent: self.root = left else: if node == node.parent.left: node.parent.left = left else: node.parent.right = left left.right = node node.parent = left ```

红黑树代码 python

相关推荐

红黑树demo python代码

red-black-tree:C - 左倾红黑树实现

matlab_ 红黑树二分搜索法示例，用于比较C++、Java、Python、Ruby和MATLAB代码

红黑树的python代码实现

python红黑树代码实现

红黑树删除python

红黑树 python 优化

生成一段python 红黑树代码

红黑树python实现

python实现红黑树

用python写生成红黑树的代码

用Python语言编写红黑树

用python 实现红黑树算法 附上代码

用python写一段红黑树的代码

帮忙写一个红黑树代码

用python学有个红黑树

红黑树节点删除示例代码

用python写一个红黑树

学习红黑树的概念及利用python代码实现红黑树三种操作和扩张

最新推荐

zigbee-cluster-library-specification

管理建模和仿真的文件

实现实时数据湖架构：Kafka与Hive集成

spring添加xml配置文件

JSBSim Reference Manual

"互动学习：行动中的多样性与论文攻读经历"

实现实时监控告警系统：Kafka与Grafana整合

输出这段Python代码输出所有3位整数中，个位是5且是3的倍数的整数

c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf

关系数据表示学习

用python 实现红黑树算法附上代码