动态平衡二叉搜索树的简易达成，Treap 树
发布时间：2021-11-22 10:44:25 所属栏目：PHP教程 来源：互联网
导读：Treap 树是一种易于实现的近似平衡的二叉搜索树。Treap 每个结点包括值和优先级两个属性，值满足二叉搜索树性质（左中右），优先级满足大顶堆的性质（左中 右中）。Treap 树的插入和删除的实现比较简单，插入结点时为待插结点随机生产一个优先级值，按照BST的
|
Treap 树是一种易于实现的近似平衡的二叉搜索树。Treap 每个结点包括值和优先级两个属性，值满足二叉搜索树性质（左<中<右），优先级满足大顶堆的性质（左<中 && 右<中）。Treap 树的插入和删除的实现比较简单，插入结点时为待插结点随机生产一个优先级值，按照BST的插入算法并通过左旋或右旋调整保持优先级大顶堆的性质；Treap树的查询复杂度期望值为 O(logN) ； public class TreapTree { public static class Node { public int v; public int p; Node lc; Node rc; public Node(int x) { v = x; p = (int)(Math.random() * Integer.MAX_VALUE); lc = null; rc = null; } } // Treap树的根结点 private Node root = null; // 检查优先级公共方法 public boolean check() { return check(root); } // 检查是否满足Treap树优先级约束 private boolean check(Node node) { if ( node == null ) return true; else { if ( node.lc != null && node.p < node.lc.p ) return false; if ( node.rc != null && node.p < node.rc.p ) return false; return ( check(node.lc) && check(node.rc) ); } } // 删除公共方法 public void delete(int x) { root = searchAndDelete(root, x); } // 删除一个结点并通过旋转保持Treap树的性质 private Node delete(Node node) { if ( node.lc == null ) { return node.rc; } else if ( node.rc == null ) { return node.lc; } else { if ( node.lc.p > node.rc.p ) { node = rotateRight(node); node.rc = delete(node.rc); } else { node = rotateLeft(node); node.lc = delete(node.lc); } return node; } } // 深度：公共方法 public int depth() { return depth(root); } // 计算树的深度 private int depth(Node node) { if ( node == null ) return 0; else { int x = depth(node.lc); int y = depth(node.rc); return ((x>y)?x:y) + 1; } } // 插入：公共方法 public void insert(int x) { root = insert(root, x); } // 插入：将新结点插入node为根的子树，子树的根可能发生变化 private Node insert(Node node, int x) { Node cur = new Node(x); if ( node == null ) { return cur; } else { if ( node.v > x ) { node.lc = insert(node.lc, x); // 如果左孩子优先级大，执行右旋 if ( node.lc.p > node.p ) return rotateRight(node); } else if ( node.v < x ) { node.rc = insert(node.rc, x); // 如果右孩子优先级大，执行左旋 if ( node.rc.p > node.p ) return rotateLeft(node); } return node; } } // 打印公共方法 public void print() { print(root); } // 中序遍历打印Treap树 private void print(Node node) { if ( node != null ) { print(node.lc); System.out.printf("%d ", node.v); print(node.rc); } } // 左旋：当前节点成为右孩子的左子树，右孩子成为根 private Node rotateLeft(Node node) { Node right = node.rc; node.rc = right.lc; right.lc = node; return right; } // 右旋：当前结点成为其左孩子的右子树，左孩子成为根 private Node rotateRight(Node node) { Node left = node.lc; node.lc = left.rc; left.rc = node; return left; } // 搜索值等于v的结点并删除它 private Node searchAndDelete(Node node, int x) { if ( node == null ) return null; else if ( node.v > x ) { node.lc = searchAndDelete(node.lc, x); } else if ( node.v < x ) { node.rc = searchAndDelete(node.rc, x); } else { node = delete(node); } return node; } // 测试 public static void main(String[] args) { TreapTree tree = new TreapTree(); for ( int i=0; i<1024; i++ ) { tree.insert(i); } for ( int i=128; i<256; i++ ) { tree.delete(i); } System.out.printf("depth : %d, check : %b%n", tree.depth(), tree.check()); tree.print(); } }  （编辑：云计算网_泰州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330476号