Python中的树形数据结构: splay树
Splay树是一种自平衡二叉搜索树，具有较好的平均和最坏情况时间复杂度。其特点在于，每次插入、查找或删除一个节点时，都将该节点通过一系列的旋转操作移动到根节点的位置，从而使树保持平衡。
下面是Python中实现Splay树的基本代码演示，其中使用字符串作为范例：
class Node: def __init__(self, value): self.value = value self.left = None self.right = None class SplayTree: def __init__(self): self.root = None def zig(self, node): parent = node.right node.right = parent.left parent.left = node return parent def zag(self, node): parent = node.left node.left = parent.right parent.right = node return parent def splay(self, node): if node == None or node == self.root: return node parent = node.parent grandparent = parent.parent if grandparent == None: if node == parent.left: self.root = self.zag(parent) else: self.root = self.zig(parent) else: if parent == grandparent.left and node == parent.left: grandparent.left = self.zag(grandparent.left) elif parent == grandparent.right and node == parent.right: grandparent.right = self.zig(grandparent.right) elif parent == grandparent.left and node == parent.right: grandparent.left = self.zig(parent) grandparent.left = self.zag(grandparent.left) else: grandparent.right = self.zag(parent) grandparent.right = self.zig(grandparent.right) self.splay(node) def insert(self, value): node = Node(value) if self.root == None: self.root = node else: parent = None temp = self.root while temp != None: parent = temp if value < temp.value: temp = temp.left else: temp = temp.right node.parent = parent if value < parent.value: parent.left = node else: parent.right = node self.splay(node) def search(self, value): temp = self.root while temp != None and temp.value != value: if value < temp.value: temp = temp.left else: temp = temp.right if temp != None: self.splay(temp) return temp def delete(self, value): node = self.search(value) if node == None: return if node.left == None: replace = node.right if replace != None: replace.parent = None elif node.right == None: replace = node.left if replace != None: replace.parent = None else: replace = node.left while replace.right != None: replace = replace.right if replace.parent != node: replace.parent.right = replace.left if replace.left != None: replace.left.parent = replace.parent replace.left = node.left replace.left.parent = replace replace.right = node.right replace.right.parent = replace if node.parent == None: self.root = replace elif node == node.parent.left: node.parent.left = replace else: node.parent.right = replace if replace != None: self.splay(replace) # sample usage tree = SplayTree() tree.insert("pican") tree.insert("dang") tree.insert("cheng") tree.insert("gong") tree.insert("ming") tree.search("gong")
相关文章