商务网站内容建设包括,网站编辑制作,怀远县建设局网站,阿里巴巴国际站怎么运营二叉搜索树 二叉查找树#xff08;Binary Search Tree#xff09;#xff0c;#xff08;又#xff1a;二叉搜索树#xff0c;二叉排序树#xff09;它或者是一棵空树#xff0c;或者是具有下列性质的二叉树#xff1a; 若它的左子树不空#xff0c;则左子树上所有结…二叉搜索树 二叉查找树Binary Search Tree又二叉搜索树二叉排序树它或者是一棵空树或者是具有下列性质的二叉树 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树。 具体介绍和实现https://blog.csdn.net/hebtu666/article/details/81741034
我们知道对于一般的二叉搜索树Binary Search Tree其期望高度即为一棵平衡树时为log2n其各操作的时间复杂度O(log2n)同时也由此而决定。但是在某些极端的情况下如在插入的序列是有序的时二叉搜索树将退化成近似链或链
此时其操作的时间复杂度将退化成线性的即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况但是在进行了多次的操作之后由于在删除时我们总是选择将待删除节点的后继代替它本身这样就会造成总是右边的节点数目减少以至于树向左偏沉。这同时也会造成树的平衡性受到破坏提高它的操作的时间复杂度。 概念引入 Abstract Self-Balancing Binary Search Tree自平衡二叉搜索树
顾名思义它在面对任意节点插入和删除时自动保持其高度
常用算法有红黑树、AVL、Treap、伸展树、SB树等。在平衡二叉搜索树中我们可以看到其高度一般都良好地维持在Ologn大大降低了操作的时间复杂度。这些结构为可变有序列表提供了有效的实现并且可以用于其他抽象数据结构例如关联数组优先级队列和集合。
对于这些结构他们都有自己的平衡性比如
AVL树
具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。
根据定义可知这是根据深度最严苛的标准了左右子树高度不能差的超过1.
具体介绍和实现https://blog.csdn.net/hebtu666/article/details/85047648 红黑树
特性: 1每个节点或者是黑色或者是红色。 2根节点是黑色。 3每个叶子节点NIL是黑色。 [注意这里叶子节点是指为空(NIL或NULL)的叶子节点] 4如果一个节点是红色的则它的子节点必须是黑色的。 5从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
根据定义确保没有一条路径会比其他路径长出2倍。 size balance tree
Size Balanced Tree简称SBT是一自平衡二叉查找树是在计算机科学中用到的一种数据结构。它是由中国广东中山纪念中学的陈启峰发明的。陈启峰于2006年底完成论文《Size Balanced Tree》并在2007年的全国青少年信息学奥林匹克竞赛冬令营中发表。由于SBT的拼写很容易找到中文谐音它常被中国的信息学竞赛选手和ACM/ICPC选手们戏称为“傻B树”、“Super BT”等。相比红黑树、AVL树等自平衡二叉查找树SBT更易于实现。据陈启峰在论文中称SBT是“目前为止速度最快的高级二叉搜索树”。SBT能在O(log n)的时间内完成所有二叉搜索树BST的相关操作而与普通二叉搜索树相比SBT仅仅加入了简洁的核心操作Maintain。由于SBT赖以保持平衡的是size域而不是其他“无用”的域它可以很方便地实现动态顺序统计中的select和rank操作。
对于SBT的每一个结点 t,有如下性质 性质(a) s[ right[t] ]≥s[ left [ left[ t ] ] ], s[ right [ left[t] ] ] 性质(b) s[ left[t] ]≥s[right[ right[t] ] ], s[ left[ right[t] ] ] 即.每棵子树的大小不小于其兄弟的子树大小。 伸展树
伸展树Splay Tree是一种二叉排序树它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。 Treap
Treap是一棵二叉排序树它的左子树和右子树分别是一个Treap和一般的二叉排序树不同的是Treap纪录一个额外的数据就是优先级。Treap在以关键码构成二叉排序树的同时还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同就是二叉堆必须是完全二叉树而Treap并不一定是。 对比可以发现AVL树对平衡性的要求比较严苛每插入一个节点就很大概率面临调整。
而红黑树对平衡性的要求没有那么严苛。可能是多次插入攒够了一下调整。。。 把每一个树的细节都扣清楚是一件挺无聊的事。。虽然据说红黑树都成了面试必问内容但是实在是不想深究那些细节这些树的基本操作也无非是那么两种左旋右旋。这些树的所有操作和情况都是这两种动作的组合罢了。
所以本文先介绍这两种基本操作等以后有时间可能到找工作时再把红黑树等结构的细节补上。 最简单的旋转 最简单的例子 这棵树左子树深度为2右子树深度为0所以根据AVL树或者红黑树的标准它都不平衡。。
那怎么办转过来 是不是就平衡了
这就是我们的顺时针旋转又叫右旋因为是以2为轴把1转下来了。
左旋同理。 带子树旋转
问题是真正转起来可没有这么简单 这才是一颗搜索树的样子啊
ABCD都代表是一颗子树。我们这三个点转了可不能不管这些子树啊对不对。
好我们想想这些子树怎么办。 首先AB子树没有关系放在原地即可。 D作为3的右子树也可以不动那剩下一个位置会不会就是放C子树呢 我们想想能否这样做。
原来 1C作为2的右子树内任何元素都比2大。
2C作为3左子树的一部分内任何元素都比3小。 转之后
1C作为2的右子树的一部分内任何元素都比2大。
2C作为3左子树内任何元素都比3小。
所以C子树可以作为3的左子树没有问题。
这样我们的操作就介绍完了。
这种基本的变换达到了看似把树变的平衡的效果。
左右旋转类似 代码实现
对于Abstract BinarySearchTree类上面网址已经给出了思路和c代码实现把java再贴出来也挺无趣的所以希望大家能自己实现。
抽象自平衡二叉搜索树AbstractSelfBalancingBinarySearchTree的所有操作都是建立在二叉搜索树BinarySearchTree 操作的基础上来进行的。
各种自平衡二叉搜索树AVL、红黑树等的操作也是由Abstract自平衡二叉搜索树的基本操作左旋、右旋构成。这个文章只写了左旋右旋基本操作供以后各种selfBalancingBinarySearchTree使用。 public abstract class AbstractSelfBalancingBinarySearchTree extends AbstractBinarySearchTree {protected Node rotateRight(Node node) {Node temp node.left;//节点2temp.parent node.parent;//节点3的父(旋转后节点2的父)node.left temp.right;//节点3接收节点2的右子树if (node.left ! null) {node.left.parent node;}temp.right node;//节点3变为节点2的右孩子node.parent temp;//原来节点3的父若存在孩子变为节点2if (temp.parent ! null) {if (node temp.parent.left) {temp.parent.left temp;} else {temp.parent.right temp;}} else {root temp;}return temp;}protected Node rotateLeft(Node node) {Node temp node.right;temp.parent node.parent;node.right temp.left;if (node.right ! null) {node.right.parent node;}temp.left node;node.parent temp;if (temp.parent ! null) {if (node temp.parent.left) {temp.parent.left temp;} else {temp.parent.right temp;}} else {root temp;}return temp;}
}
