网站建设好吗,湖南装修公司排名10名,美丽乡村建设网站模板,wordpress标题连接符前置 本篇是平衡树-treap的补充学习笔记。 Treap - 树堆 学习基础#xff1a;适合一定基础的#xff1a;比如#xff0c;实现了经典二叉搜索树#xff08;常用的几个函数写过#xff09;#xff0c; 和二叉堆#xff08;数组的上浮下沉会写吗#xff1f;#xff09;适合一定基础的比如实现了经典二叉搜索树常用的几个函数写过 和二叉堆数组的上浮下沉会写吗至少了解旋转的概念且写过旋转的接口有一定理解比如实现AVL树/红黑树涉及到相关思想。 实现语言Java。 —其它语言的小伙伴可拷贝我的代码转译成自己的语言笔者虽然多语言学习但使用侧重点不同 对语言的理解也浅薄 频繁切换语言不妥。 纯根据理解手写。 来源算法导论---红黑树章节后的treap思考题 参考书籍:算法导论 有关问题算法导论第6章堆排序详细地说明了:二叉堆概念 上浮和下沉操作的相关概念伪代码。实现一下二叉堆优先级队列算法导论第12章介绍了transplant接口, 和二叉搜索树的其它好用的函数。算法导论第13章介绍了红黑树 红黑树的代码很难写且不易理解只需了解一下旋转这个操作和伪代码即可。可以去油管或者b站 或者搜索引擎查找相关问题。
笔者水平有限 本篇基于笔记改写 缺点很多 不太适合新手 适合部分熟悉的朋友回顾复习 在此见谅。
引入
对于一般的二叉搜索树 已知n个数据序列插入到一个二叉搜索树有可能得到性能极差高度极不平衡的二叉搜索树。这种单支树的例子 相信你已经不会陌生了。对于随机化构建的二叉搜索树 经过概率论分析的数学期望 得到的二叉搜索树是趋向平衡的。 之前写过一篇动态随机化的平衡树结构-----跳表, 非形式地讨论了这个问题。 接下来 介绍另一种动态随机化的平衡树结构-----Treap。 为什么有了随机化构建 而依旧有研究动态化构建的必要呢 尽管在跳表篇给了解释 但此篇为不甚了解的朋友作出非严格地说明。已知n个数据构建随机二叉搜索树 当然可行。 缺点 如果我们未知数据量n呢或者随机化二叉搜索树我们还要动态地插入删除呢 在只允许我们一次取一个数据的场景 经典的随机化构建二叉搜索树不现实了。 我都拿不到所有数据如何随机化地插入二叉搜索树呢 相比Treap和跳表动态树结构 经典随机二叉搜索树可以说是静态结构。 介绍
Treap 是一种弱平衡的树结构 什么叫做弱平衡呢 不同平衡树对平衡的定义不同 确切的它们对平衡的宏观定义是相同的维持一棵好性能的树 但对树的平衡严格程度要求是不一样的。
一般地 弱平衡树更好实现 相比于强平衡的AVL左右子树高度差不为1 红黑树左右高度差小于2倍 跳表明显好实现多了。其次强平衡树在高度上有最坏的保证最坏也是性能比较好的弱平衡树最坏保证是经典二叉搜索树的最坏情况单支链表的情况。 归咎原因 弱平衡没有在高度上严格保证 这里的Treap还把基本操作交给概率这一事物 平均来看很好 但失败的后果会很糟糕虽然失败导致最坏的情况从概率数字来看几乎不可能发生。
现在我们可以正式地介绍一下Treap了 在此简单回顾一下 对于二叉搜索树 基本性质 左子树的key 根 右子树的key。 对于二叉堆基本性质孩子的key父亲的key(最小堆), 兄弟之间的大小关系不在意。 综合二者性质依旧让key的关系满足: 左 根 右 可以取等自己调整一下。但我个人风格是key最好互异。 堆的性质从何体现 我们引入了一个priority字段表示优先级。 类比二叉堆的最小堆 那么最小Treap,满足parent.priority node.priority 综合 Treap 具有以下几个重要性质 二叉搜索树性质对于每个节点其左子树的所有节点的键值小于该节点的键值而右子树的所有节点的键值大于该节点的键值。假设键值是不一样的。 堆性质每个节点的优先级大于或等于其子节点的优先级。这条性质导致这个结构和堆一致。 随机性节点的优先级通常是随机生成器如Java中的Random对象生成的这使得 Treap 的结构在插入和删除操作中保持平均 O ( l o g n ) O(log n) O(logn) 的时间复杂度。 动态平衡性支持随机化的动态插入删除 比随机化二叉搜索树自由。
实现
以下代码比较简单 若你是学Java的应该不难读懂其它语言的小伙伴可以借助chatgpt翻译成自己的语言,这是一种我比较经典的写法了。 import java.util.Random;
import java.util.Comparator;
public class TreapK,V { //比较器 可以手动传递比较器对象 否则K必须实现Comparable接口 private Comparator? super K comparator; //随机数生成器 为每一个节点生成一个随机数 private final Random random new Random(); private NodeK,V root; //根节点 public class NodeK,V{ K key; //键 V value; //值 NodeK,V left; //左子树 NodeK,V right; //右子树 NodeK,V parent; //父指针 int priority; //优先级 public Node(K key, V value) { this.key key; this.value value; left right parent null; priority random.nextInt();//为新生成的节点分配一个随机数。 } } public Treap(){ this(null); } public Treap(Comparator? super K comparator) { this.comparator comparator; }
}查询操作 查询操作 方法思路同经典二叉搜索树 在此不多赘述。
下面实现了三个方法 核心关注search方法 contains返回一个布尔值判断关键字key的节点是否存在。get方法根据键获取值。
public NodeK,V search(K key){ if(root null){ return null; //这里单独检查一下。} NodeK,V current root;//遍历Treap int cmp 0; //记录比较结果if(comparator ! null){ //比较器不为空那么优先使用比较器。 while(current!null){ cmp comparator.compare(current.key, key); if(cmp0){ return current;//找到了直接返回节点的引用。 } else if(cmp0){ //当前值太小了 前往右子树current current.right; } else{ //cmp0 current current.left; } } } else{ //comparator null SuppressWarnings(unchecked!) Comparable? super K comparable (Comparable? super K)current.key; // 使用者必须确保K类型是可比较的 否则报错。 cmp comparable.compareTo(key); while(current ! null){ comparable (Comparable? super K)current.key; cmp comparable.compareTo(key); //逻辑与比较器相同if(cmp0){ return current; } else if(cmp0){ current current.right; } else{ current current.left; } } } return null;//出循环了即为空。
}
//根据serach结果造contains函数和get函数
public boolean contains(K key){ return search(key) ! null;
} public V get(K key){ return search(key) ! null ? search(key).value : null;
}插入操作
写法很简单 套路更简单。 经典BST插入二叉堆的上浮调整。
TREAP-INSERT(T, x):y - T.rootp - NILwhile y ≠ NIL:p - yif y.key x.key:// Update the valuey.val - x.valreturnelseif y.key x.key:y - y.leftelse: // y.key x.keyy - y.rightif p NIL:T.root - x // Insert as root if tree was emptyelseif p.left y:p.left - xelse:p.right - xsiftUp(T, x) // Perform the sift up operation
这张图举例 BST操作不多说 下面来说明指针版本的上浮操作处理 旋转又来了。 可能数组的堆上浮写熟悉了, 头一次处理指针版本的。 public void put(K key, V value){ if(key ! null) { insert(new Node(key, value)); }
}
public void insert(K key, V value){ if(key ! null) { insert(new Node(key, value)); }
}
public void insert(NodeK,V node) { if (root null) { root node; //这里单独处理 保证后续代码在非空情形下return; } NodeK,V current root; // 当前节点 NodeK,V parent null; // 父节点 int cmp 0; // 遍历查找插入位置 while (current ! null) { parent current; if (comparator ! null) { cmp comparator.compare(node.key, current.key); } else { SuppressWarnings(unchecked) Comparable? super K comparable (Comparable? super K) current.key; cmp comparable.compareTo(node.key); } if (cmp 0) { current.value node.value; // 更新值 return; } else if (cmp 0) { current current.right; // 前往右子树 } else { current current.left; // 前往左子树 } } // 插入节点 node.parent parent; if (cmp 0) { parent.right node; // 插入到右子树 } else { parent.left node; // 插入到左子树 } siftUp(node); // 上浮操作
}旋转接口
这里眼熟一下 实现avl或者红黑树简单回顾一下左旋和右旋两个接口。
private void leftRotate(NodeK,V x) {NodeK,V y x.right;x.right y.left;if (y.left ! null) {y.left.parent x;}y.parent x.parent;if (x.parent null) {root y; // y 变为新的根节点} else if (x x.parent.left) {x.parent.left y; // x 是左子节点} else {x.parent.right y; // x 是右子节点}y.left x; // x 变为 y 的左子节点x.parent y; // 更新 x 的父指针
}private void rightRotate(NodeK,V y) {NodeK,V x y.left;y.left x.right;if (x.right ! null) {x.right.parent y;}x.parent y.parent;if (y.parent null) {root x; // x 变为新的根节点} else if (y y.parent.left) {y.parent.left x; // y 是左子节点} else {y.parent.right x; // y 是右子节点}x.right y; // y 变为 x 的右子节点y.parent x; // 更新 y 的父指针
}
siftUp private void siftUp(NodeK, V node){ //上浮的临界是根节点到根节点就必须终止了。 //这里直接node.parent 不需要申请新变量。---对可读性没多大英影响 while(node ! root node.priority node.parent.priority){ //开始上浮 if(node.parent.left node){ //执行右旋 rightRotate(node.parent); } else{ //parent.right node //执行左旋 leftRotate(node.parent); } //经过旋转后原先的父亲节点指针parent成为node的孩子节点 node.parent node.parent; }
}删除
以下两个接口函数 你必须在BST中学明白了。 这两个方法在Treap的删除操作中非常重要。
transplant minimum
transplant 方法用于替换树中一个节点 u 为另一个节点 v并更新它们的父节点关系。minimum 方法用于查找给定节点的最小值节点通过遍历左子树实现。
private void transplant(NodeK,V u, NodeK,V v) {if (u.parent null) {root v; // u 是根节点} else if (u u.parent.left) {u.parent.left v; // u 是左子节点} else {u.parent.right v; // u 是右子节点}if (v ! null) {v.parent u.parent; // 更新 v 的父指针}
}public NodeK,V minimum(NodeK,V node) {if (node null) {return null; // 如果节点为空返回 null}while (node.left ! null) {node node.left; // 一直遍历左子树直到找到最小值}return node;
}删除
public void delete(NodeK,V node) {if (node.left null) {transplant(node, node.right); // 只有右子树} else if (node.right null) {transplant(node, node.left); // 只有左子树} else {// 找到右子树中的最小节点NodeK,V leftMin minimum(node.right);if (leftMin.parent ! node) {transplant(leftMin, leftMin.right);leftMin.right node.right;if (leftMin.right ! null) {leftMin.right.parent leftMin;}}transplant(node, leftMin);leftMin.left node.left;leftMin.left.parent leftMin;}siftDown(node); // 维护 Treap 的性质
}
siftDown
private void siftDown(NodeK,V node) {NodeK,V child node.left;boolean isLeft true;//左孩子还是右孩子while (child ! null) {// 选择优先级较高的孩子节点if (node.right ! null node.right.priority child.priority) {child node.right;isLeft false;}// 执行旋转if (child.priority node.priority) {if (isLeft) {rightRotate(node);} else {leftRotate(node);}node child; // 更新当前节点为孩子节点child (isLeft) ? node.left : node.right; // 继续下沉isLeft true; // 重置为左子树} else {break; // 如果当前节点的优先级已大于所有孩子结束}}
}
其它问题思考
Treap的唯一性
给定一组关键字和优先级均互异的节点 可以组成唯一的Treap树与这些节点关联。 第一步 根的唯一性根节点是具有最高优先级的节点 由于每个键值的优先级是唯一的所以具有最高优先级的节点也是唯一的。比如最小Treap中根节点是最小的priority。 第二步 递归构建。 由于根节点唯一了 那么可以分组一组的节点的key均小于root.key, 另一组均大于root.key。那么左右两边的序列元素确定了。 第三步 递归中子树遵循第一条 因此结构必定唯一。 因为树是由递归定义的。
以上性质涉及二叉搜索树的有序性 堆的性质。总之 可以证明满足上述条件的Treap具有唯一性。 证毕
待补充。。。
由于其它问题比如树的期望高度证明需要概率知识 数学这一块依旧是硬伤。 在此就不献丑了 留待日后补充。
总源码
关于Treap实现有多种方案。 比如我的方案是旋转treap,可以参考treap。 有兴趣的小伙伴可以根据我的代码拓展很多功能 在此篇就不写多了 只能说本篇的可拓展性强吧 学艺不精 难免错误 希望并感谢大佬您提出宝贵的意见 谢邀。 感谢我的朋友们的鼓励和数学编程问题的指导 这几天精神真是颓废 今天好多了。
import java.util.Random;
import java.util.Comparator;
public class TreapK,V { //比较器 可以手动传递比较器对象 否则K必须实现Comparable接口 private Comparator? super K comparator; //随机数生成器 为每一个节点生成一个随机数 private final Random random new Random(); private NodeK,V root; //根节点 public class NodeK,V{ K key; //键 V value; //值 NodeK,V left; //左子树 NodeK,V right; //右子树 NodeK,V parent; //父指针 int priority; //优先级 public Node(K key, V value) { this.key key; this.value value; left right parent null; priority random.nextInt();//为新生成的节点分配一个随机数。 } } public Treap(){ this(null); } public Treap(Comparator? super K comparator) { this.comparator comparator; }
public NodeK,V search(K key){ if(root null){ return null; //这里单独检查一下。} NodeK,V current root;//遍历Treap int cmp 0; //记录比较结果if(comparator ! null){ //比较器不为空那么优先使用比较器。 while(current!null){ cmp comparator.compare(current.key, key); if(cmp0){ return current;//找到了直接返回节点的引用。 } else if(cmp0){ //当前值太小了 前往右子树current current.right; } else{ //cmp0 current current.left; } } } else{ //comparator null SuppressWarnings(unchecked!) Comparable? super K comparable (Comparable? super K)current.key; // 使用者必须确保K类型是可比较的 否则报错。 cmp comparable.compareTo(key); while(current ! null){ comparable (Comparable? super K)current.key; cmp comparable.compareTo(key); //逻辑与比较器相同if(cmp0){ return current; } else if(cmp0){ current current.right; } else{ current current.left; } } } return null;//出循环了即为空。
}
//根据serach结果造contains函数和get函数
public boolean contains(K key){ return search(key) ! null;
} public V get(K key){ return search(key) ! null ? search(key).value : null;
}
public void put(K key, V value){ if(key ! null) { insert(new Node(key, value)); }
}
public void insert(K key, V value){ if(key ! null) { insert(new Node(key, value)); }
}
public void insert(NodeK,V node) { if (root null) { root node; //这里单独处理 保证后续代码在非空情形下return; } NodeK,V current root; // 当前节点 NodeK,V parent null; // 父节点 int cmp 0; // 遍历查找插入位置 while (current ! null) { parent current; if (comparator ! null) { cmp comparator.compare(node.key, current.key); } else { SuppressWarnings(unchecked) Comparable? super K comparable (Comparable? super K) current.key; cmp comparable.compareTo(node.key); } if (cmp 0) { current.value node.value; // 更新值 return; } else if (cmp 0) { current current.right; // 前往右子树 } else { current current.left; // 前往左子树 } } // 插入节点 node.parent parent; if (cmp 0) { parent.right node; // 插入到右子树 } else { parent.left node; // 插入到左子树 } siftUp(node); // 上浮操作
}
private void leftRotate(NodeK,V x) {NodeK,V y x.right;x.right y.left;if (y.left ! null) {y.left.parent x;}y.parent x.parent;if (x.parent null) {root y; // y 变为新的根节点} else if (x x.parent.left) {x.parent.left y; // x 是左子节点} else {x.parent.right y; // x 是右子节点}y.left x; // x 变为 y 的左子节点x.parent y; // 更新 x 的父指针
}private void rightRotate(NodeK,V y) {NodeK,V x y.left;y.left x.right;if (x.right ! null) {x.right.parent y;}x.parent y.parent;if (y.parent null) {root x; // x 变为新的根节点} else if (y y.parent.left) {y.parent.left x; // y 是左子节点} else {y.parent.right x; // y 是右子节点}x.right y; // y 变为 x 的右子节点y.parent x; // 更新 y 的父指针
}
private void siftUp(NodeK, V node){ //上浮的临界是根节点到根节点就必须终止了。 //这里直接node.parent 不需要申请新变量。---对可读性没多大英影响 while(node ! root node.priority node.parent.priority){ //开始上浮 if(node.parent.left node){ //执行右旋 rightRotate(node.parent); } else{ //parent.right node //执行左旋 leftRotate(node.parent); } //经过旋转后原先的父亲节点指针parent成为node的孩子节点 node.parent node.parent; }
}
private void transplant(NodeK,V u, NodeK,V v) {if (u.parent null) {root v; // u 是根节点} else if (u u.parent.left) {u.parent.left v; // u 是左子节点} else {u.parent.right v; // u 是右子节点}if (v ! null) {v.parent u.parent; // 更新 v 的父指针}
}public NodeK,V minimum(NodeK,V node) {if (node null) {return null; // 如果节点为空返回 null}while (node.left ! null) {node node.left; // 一直遍历左子树直到找到最小值}return node;
}
public void delete(NodeK,V node) {if (node.left null) {transplant(node, node.right); // 只有右子树} else if (node.right null) {transplant(node, node.left); // 只有左子树} else {// 找到右子树中的最小节点NodeK,V leftMin minimum(node.right);if (leftMin.parent ! node) {transplant(leftMin, leftMin.right);leftMin.right node.right;if (leftMin.right ! null) {leftMin.right.parent leftMin;}}transplant(node, leftMin);leftMin.left node.left;leftMin.left.parent leftMin;}siftDown(node); // 维护 Treap 的性质
}
private void siftDown(NodeK,V node) {NodeK,V child node.left;boolean isLeft true;//左孩子还是右孩子while (child ! null) {// 选择优先级较高的孩子节点if (node.right ! null node.right.priority child.priority) {child node.right;isLeft false;}// 执行旋转if (child.priority node.priority) {if (isLeft) {rightRotate(node);} else {leftRotate(node);}node child; // 更新当前节点为孩子节点child (isLeft) ? node.left : node.right; // 继续下沉isLeft true; // 重置为左子树} else {break; // 如果当前节点的优先级已大于所有孩子结束}}
}
}
红尘漩涡不由己 何朝散发弄扁舟。 乘风破浪三万里 方是我辈魔道人。 —20240927 — authorAutumn Whisper。
