Python中的树形数据结构: 随机化平衡树
Python中的树形数据结构有很多种，其中一种比较常见的是随机化平衡树。它是一种自平衡二叉搜索树，可以高效地支持查找、插入和删除操作。
随机化平衡树的基本思想是利用随机化的方法来保证树的平衡性，即任意节点的左右子树的深度差不超过1。具体来说，插入和删除操作时，每个节点都有一定的概率被选择为旋转的中心，以保证树的平衡性。
下面是一个简单的随机化平衡树的实现：
import random class Node: def __init__(self, key): self.key = key self.left = None self.right = None self.size = 1 class RandomizedBST: def __init__(self): self.root = None def size(self, node): return node.size if node else 0 def update_size(self, node): node.size = self.size(node.left) + self.size(node.right) + 1 def rotate_left(self, node): x = node.right node.right = x.left x.left = node self.update_size(node) self.update_size(x) return x def rotate_right(self, node): x = node.left node.left = x.right x.right = node self.update_size(node) self.update_size(x) return x def insert(self, key): self.root = self._insert(self.root, key) def _insert(self, node, key): if not node: return Node(key) if key < node.key: node.left = self._insert(node.left, key) if random.random() * self.size(node) < self.size(node.left): node = self.rotate_right(node) else: node.right = self._insert(node.right, key) if random.random() * self.size(node) < self.size(node.right): node = self.rotate_left(node) self.update_size(node) return node def delete(self, key): self.root = self._delete(self.root, key) def _delete(self, node, key): if not node: return None if key < node.key: node.left = self._delete(node.left, key) elif key > node.key: node.right = self._delete(node.right, key) else: if not node.left: return node.right if not node.right: return node.left if random.random() < 0.5: x = node.left while x.right: x = x.right node.key = x.key node.left = self._delete(node.left, x.key) else: x = node.right while x.left: x = x.left node.key = x.key node.right = self._delete(node.right, x.key) self.update_size(node) return node def search(self, key): node = self.root while node and node.key != key: node = node.left if key < node.key else node.right return node def inorder(self, node): if node: self.inorder(node.left) print(node.key, end=' ') self.inorder(node.right) def __repr__(self): s = [] self._repr(self.root, s, 0) return '\n'.join(s) def _repr(self, node, s, level): if node: self._repr(node.right, s, level + 1) s.append(' ' * level + str(node.key)) self._repr(node.left, s, level + 1)
代码中，Node类表示树的节点，包含键值、左右子节点和子树大小等信息。RandomizedBST类表示随机化平衡树，包含插入、删除、查找、遍历等方法。其中，插入和删除操作使用随机化的方法来保证树的平衡性，同时更新节点的子树大小信息。遍历操作按照中序遍历的顺序输出树中的所有节点。
下面是一个使用字符串作为范例的演示：
>>> bst = RandomizedBST() >>> bst.insert('p') >>> bst.insert('i') >>> bst.insert('d') >>> bst.insert('a') >>> bst.insert('n') >>> bst.insert('c') >>> bst.insert('o') >>> bst.insert('d') >>> print(bst) p o n i d c a >>> bst.delete('o') >>> print(bst) p n i d c a >>> node = bst.search('c') >>> print(node.key) c
相关文章