treap Python实现

# coding=utf-8 # treap(树堆)Python实现 import random def preorder_tree_walk(node): if node: print node.key, node.priority preorder_tree_walk(node.left) preorder_tree_walk(node.right) def left_rotate(tree, node): node_right = node.right if not node.p: tree.root = node_right elif node == node.p.left: node.p.left = node_right else: node.p.right = node_right node_right.p = node.p node.right = node_right.left if node_right.left: node_right.left.p = node node_right.left = node node.p = node_right def right_rotate(tree, node): node_left = node.left if not node.p: tree.root = node_left elif node == node.p.left: node.p.left = node_left else: node.p.right = node_left node_left.p = node.p node.left = node_left.right if node_left.right: node_left.right.p = node node_left.right = node node.p = node_left class TreapNode(object): def __init__(self, key, priority): self.key = key self.priority = priority self.left = None self.right = None self.p = None class Treap(object): def __init__(self): self.root = None def find(self, key): temp_root = self.root while temp_root: if key < temp_root.key: temp_root = temp_root.left elif key > temp_root.key: temp_root = temp_root.right else: return temp_root return None def insert(self, node): temp_root = self.root temp_node = None while temp_root: temp_node = temp_root if node.key > temp_node.key: temp_root = temp_root.right elif node.key < temp_node.key: temp_root = temp_root.left else: raise KeyError, "Error" if not temp_node: self.root = node return elif node.key < temp_node.key: temp_node.left = node node.p = temp_node elif node.key > temp_node.key: temp_node.right = node node.p = temp_node self.fixup(temp_node, node) def fixup(self, father, child): if father: if child == father.left and child.priority < father.priority: right_rotate(self, father) elif child == father.right and child.priority < father.priority: left_rotate(self, father) self.fixup(father.p, father) def delete(self, key): node = self.root while node: if key < node.key: node = node.left elif key > node.key: node = node.right else: break if not node: raise KeyError, "Error!" flag = 1 while flag: if not node.left: if node.right: node.right.p = node.p if node.p: if node == node.p.left: node.p.left = node.right else: node.p.right = node.right else: self.root = node.right flag = 0 elif not node.right: if node.left: node.left.p = node.p if node.p: if node == node.p.left: node.p.left = node.left else: node.p.right = node.left else: self.root = node.left flag = 0 else: # 如果左右子节点均存在 那么把 priority 值大的放到根节点的位置上 网上给的是递归实现 那有没有可能可以递推实现呢？ # 答案是 有可能的 if node.left.priority < node.right.priority: right_rotate(self, node) else: left_rotate(self, node) def main(): number_list = (7, 4, 1, 8, 5, 2, 9, 6, 3) tree = Treap() for number in number_list: priority = random.randint(1, 100) node = TreapNode(number, priority) tree.insert(node) preorder_tree_walk(tree.root) print '==========' tree.delete(4) preorder_tree_walk(tree.root) if __name__ == '__main__': main() 网上一些资料都是递归实现的插入和删除, Python由于没有按引用传递, 所以暂时没有想到好的办法来递归实现, 只好递推实现。注:暂时没有时间写实现思路，等过一段时间补上End.

转载于:https://www.cnblogs.com/wuditju/p/6004399.html