长沙做公司网站,网页制作实训总结800字,用asp做的网站有多少,wordpress docker中文文档我们知道AVL树为了保持严格的平衡#xff0c;所以在数据插入上会呈现过多的旋转#xff0c;影响了插入和删除的性能#xff0c;此时AVL的一个变种伸展树#xff08;Splay#xff09;就应运而生了#xff0c;我们知道万事万物都遵循一个“八二原则“#xff0c;也就是说8… 我们知道AVL树为了保持严格的平衡所以在数据插入上会呈现过多的旋转影响了插入和删除的性能此时AVL的一个变种伸展树Splay就应运而生了我们知道万事万物都遵循一个“八二原则“也就是说80%的人只会用到20%的数据比如说我们的“QQ输入法”平常打的字也就那么多或许还没有20%呢。一伸展树 1思想伸展树的原理就是这样的一个”八二原则”比如我要查询树中的“节点7”如果我们是AVL的思路每次都查询“节点7”那么当这棵树中的节点越来越多的情况下就会呈现下旋所以复杂度只会递增伸展树的想法就是在第一次查询时树里面会经过一阵痉挛把“节点7”顶成“根节点”操作类似AVL的双旋转比如下图:当我们再次查询同样的”数字7“时直接在根节点处O1取出当然这算是一个最理想的情况有时痉挛过度会出现糟糕的”链表“也就退化了到O(N)所以伸展树讲究的是”摊还时间“意思就是说在”连续的一系列操作中的平均时间“当然可以保证是logN。2伸展方式不知道大家可否记得在AVL中的旋转要分4个情况同样伸展树中的伸展需要考虑6种情况当然不考虑镜像的话也就是3种情况从树的伸展方向上来说有“自下而上”和“自上而下的两种方式考虑到代码实现简洁我还是说下后者。1) 自上而下的伸展这种伸展方式会把树切成三份L树M树R树考虑的情况有单旋转“一字型”旋转“之字形”旋转。单旋转从图中我们可以看到要将“节点2”插入到根上需要将接近于“节点2”的数插入到根上也就是这里的“节点7”首先树被分成了3份初始情况L和R树是“空节点”M是整棵树现在需要我们一步一步拆分当我们将“节点2”试插入到“节点7”的左孩子时发现“节点7”就是父节点满足“单旋转”情况然后我们将整棵树放到“R树”中的left节点上M此时是一个逻辑上的空节点然后我们将R树追加到M树中。L树追加到M的左子树中最后我们将“节点2”插入到根节点上。说这么多有点拗口伸展树比较难懂需要大家仔细品味一下。一字型一字型旋转方式与我们AVL中的“单旋转”类似首先同样我们切成了三份当我们预插入20时”发现20的“父节点”是根的右孩子而我们要插入的数字又在父节点的右边此时满足”一字型“旋转我们将710两个节点按照”右右情况”旋转旋转后“节点10的左孩子放入到L树的right节点节点10”作为中间树M最后将20插入根节点。之字形之字形有点类似AVL中的“双旋转”不过人家采取的策略是不一样的当我们试插入“节点9”同样发现“父节点”是根的右儿子并且“节点9”要插入到父节点的内侧根据规则需要将“父节点10”作为M树中的根节点“节点7”作为L树中的right节点然后M拼接L和R最后将节点9插入到根上。3基本操作1) 节点定义我们还是采用普通二叉树中的节点定义也就没有了AVL那么烦人的高度信息。
public class BinaryNodeT{// Constructorspublic BinaryNode(T theElement) : this(theElement, null, null) { }public BinaryNode(T theElement, BinaryNodeT lt, BinaryNodeT rt){element theElement;left lt;right rt;}public T element;public BinaryNodeT left;public BinaryNodeT right;}2) 伸展这里为了编写代码方便我采用的是逻辑nullNode节点具体伸展逻辑大家可以看上面的图。
#region 伸展/// summary/// 伸展/// /summary/// param nameKey/param/// param nametree/param/// returns/returnspublic BinaryNodeT Splay(T Key, BinaryNodeT tree){BinaryNodeT leftTreeMax, rightTreeMin;header.left header.right nullNode;leftTreeMax rightTreeMin header;nullNode.element Key;while (true){int compareResult Key.CompareTo(tree.element);if (compareResult 0){//如果成立说明是”一字型“旋转if (Key.CompareTo(tree.left.element) 0)tree rotateWithLeftChild(tree);if (tree.left nullNode)break;//动态的将中间树的”当前节点“追加到 R 树中同时备份在header中rightTreeMin.left tree;rightTreeMin tree;tree tree.left;}else if (compareResult 0){//如果成立说明是”一字型“旋转if (Key.CompareTo(tree.right.element) 0)tree rotateWithRightChild(tree);if (tree.right nullNode)break;//动态的将中间树的”当前节点“追加到 L 树中同时备份在header中leftTreeMax.right tree;leftTreeMax tree;tree tree.right;}else{break;}}/* 剥到最后一层来最后一次切分 *///把中间树的左孩子给“左树”leftTreeMax.right tree.left;//把中间树的右孩子给“右树”rightTreeMin.left tree.right;/* 合并操作 *///将头节点的左树作为中间树的左孩子tree.left header.right;//将头结点的右树作为中间树的右孩子tree.right header.left;return tree;}#endregion3) 插入插入操作关键在于我们要找到接近于”要插入点“的节点然后顶成“根节点”也就是上面三分图中的最后一分。
#region 插入/// summary/// 插入/// /summary/// param nameKey/parampublic void Insert(T Key){if (newNode null)newNode new BinaryNodeT(default(T));newNode.element Key;if (root nullNode){newNode.left newNode.right nullNode;root newNode;}else{root Splay(Key, root);int compareResult Key.CompareTo(root.element);if (compareResult 0){newNode.left root.left;newNode.right root;root.left nullNode;root newNode;}elseif (compareResult 0){newNode.right root.right;newNode.left root;root.right nullNode;root newNode;}elsereturn;}newNode null;}#endregion4) 删除删除操作也要将节点伸展到根上然后进行删除逻辑很简单。
#region 删除/// summary/// 删除/// /summary/// param nameKey/parampublic void Remove(T Key){BinaryNodeT newTree;//将删除结点顶到根节点root Splay(Key, root);//不等于说明没有找到if (root.element.CompareTo(Key) ! 0)return;//如果左边为空则直接用root的右孩子接上去if (root.left nullNode){newTree root.right;}else{newTree root.left;newTree Splay(Key, newTree);newTree.right root.right;}root newTree;}#endregion伸展树可以总结成一幅图
