郑州 手机网站,淘客推广渠道,深圳外贸网站设计,WordPress手机APP源码目录 一、基本介绍
二、伸展操作
1. 左右情况的伸展
2. 左左情况的伸展
3. 右左情况的伸展
4. 右右情况的伸展
三、其它操作
1. 插入
2. 删除
四、代码实现 一、基本介绍
伸展树是一种二叉搜索树#xff0c;伸展树也是一种平衡树#xff0c;不过伸展树并不像AVL树那…目录 一、基本介绍
二、伸展操作
1. 左右情况的伸展
2. 左左情况的伸展
3. 右左情况的伸展
4. 右右情况的伸展
三、其它操作
1. 插入
2. 删除
四、代码实现 一、基本介绍
伸展树是一种二叉搜索树伸展树也是一种平衡树不过伸展树并不像AVL树那样对树的平衡有很
严格的要求左右孩子高度之差不能超过1伸展树通过一系列的伸展操作可以保证对伸展树
的任意连续M次操作其时间复杂度不会超过MlogN级别并且伸展树的实现相较于AVL树也简单
了很多不论是插入还是删除算法
二、伸展操作
伸展树之所以能够保证MlogN的界就是因为伸展树的伸展操作每一次调用伸展树的search方法
查找一个结点的时候如果存在那么就需要对该结点进行一系列的伸展操作经过一系列的伸展
操作之后该结点最终会变成根节点
1. 左右情况的伸展
本质上就是AVL树的右双旋转 2. 左左情况的伸展
这种情况和AVL树的单右旋转不同需要先将A进行单向左旋然后再将B进行单向左旋 3. 右左情况的伸展
略情况同1
4. 右右情况的伸展
略情况同2
三、其它操作
1. 插入
伸展树的插入就是普通BST的插入算法无差别
2. 删除
伸展树的删除步骤如下
1找到被删除的结点D的左子树DL的最大结点M然后将M结点伸展到DL的根节点处
2然后将D删除因为M一定没有右孩子即使被伸展到DL的根节点也不会有右孩子此时只
需要将D的右子树DR挂到M的右孩子上即可
四、代码实现
package splaytree;/*** 实现伸展树** author CodingW*/
public class SplayTreeK extends ComparableK, V {private TreeNodeK, V root;/*** 向伸展树中插入一个新的结点** param key 关键字* param value 值*/public void insert(K key, V value) {TreeNodeK, V cur root;TreeNodeK, V pre null;while (cur ! null) {int cmp cur.key.compareTo(key);if (cmp 0) {pre cur;cur cur.right;} else if (cmp 0) {pre cur;cur cur.left;} else {// 如果相等那么就进行替换cur.value value;break;}}TreeNodeK, V node new TreeNode(key, value);node.setParent(pre);if (pre null) {// 说明当前插入的结点是根节点root node;return;}// 如果pre不为null那么说明cur不为null即// root不为null所以pre一定指向的是bst中// node需要插入位置的前驱结点if (pre.key.compareTo(key) 0) {pre.right node;} else {pre.left node;}}/*** 返回先序遍历** return 返回先序遍历序列字符串*/public String preOrder() {StringBuilder pre new StringBuilder();if (root null) {return pre.toString();}TreeNodeK, V cur root;while (cur ! null) {if (cur.left ! null) {TreeNodeK, V mostRight cur.left;while (mostRight.right ! null mostRight.right ! cur) {mostRight mostRight.right;}if (mostRight.right null) {pre.append({).append(cur.key).append(,).append(cur.value).append(,).append(cur.parent null ? null : cur.parent.value).append(}\t);mostRight.right cur;cur cur.left;continue;} else {mostRight.right null;}} else {pre.append({).append(cur.key).append(,).append(cur.value).append(,).append(cur.parent null ? null : cur.parent.value).append(}\t);}cur cur.right;}return pre.toString();}public String inOrder() {StringBuilder in new StringBuilder();if (root null) {return in.toString();}TreeNodeK, V cur root;while (cur ! null) {if (cur.left ! null) {TreeNodeK, V mostRight cur.left;while (mostRight.right ! null mostRight.right ! cur) {mostRight mostRight.right;}if (mostRight.right null) {mostRight.right cur;cur cur.left;continue;} else {mostRight.right null;in.append({).append(cur.key).append(,).append(cur.value).append(,).append(cur.parent null ? null : cur.parent.value).append(}\t);}} else {in.append({).append(cur.key).append(,).append(cur.value).append(,).append(cur.parent null ? null : cur.parent.value).append(}\t);}cur cur.right;}return in.toString();}/*** 删除伸展树指定的关键字基本的删除算法的思想是* 首先查找这个被删除的元素然后这个元素就会变成根元素* 然后删除这个根元素同时查找其左子树的最大值这个最大值* 也会变成根元素这个根元素一定右子树为空那么把这个根元素的** param key 关键字* return 返回被删除的关键字对应的值*/public V delete(K key) {TreeNodeK, V node searchHelper(key);if (node null) {return null;}// 找到node的左孩子的最大值TreeNodeK, V leftMax findMax(node.left);// 将左孩子的最大值伸展到根节点leftMax一定是没有右孩子的// 因为leftMax的伸展百分之百是left-left型伸展之后是right-right型// 后面的伸展只能在这两个型之间跳跃splaying(leftMax);leftMax.right node.right;node.left null;node.right null;return node.value;}private TreeNodeK, V findMax(TreeNodeK, V root) {while (root ! null root.right ! null) {root root.right;}return root;}/*** 单向右旋转** param node 被旋转的结点*/private void singleRightRotate(TreeNodeK, V node) {// 特别注意在旋转过程中更新结点的父亲指针否则将会导致回溯// 过程中产生某些意外情况TreeNodeK, V left node.left;node.left left.right;if (left.right ! null) {left.right.parent node;}left.parent node.parent;if (node.parent null) {// 如果当前旋转的是根节点root left;} else if (node node.parent.left) {node.parent.left left;} else {node.parent.right left;}left.right node;node.parent left;}/*** 单向左旋转** param node 被旋转的结点*/private void singleLeftRotate(TreeNodeK, V node) {TreeNodeK, V right node.right;node.right right.left;if (right.left ! null) {right.left.parent node;}right.parent node.parent;if (node.parent null) {root right;} else if (node node.parent.left) {node.parent.left right;} else {node.parent.right right;}right.left node;node.parent right;}/*** 双向右旋转** param node 被旋转的结点*/private void doubleRightRotate(TreeNodeK, V node) {singleLeftRotate(node.left);singleRightRotate(node);}/*** 双向左旋转** param node 被旋转的结点*/private void doubleLeftRotate(TreeNodeK, V node) {singleRightRotate(node.right);singleLeftRotate(node);}/*** 根据关键字查找指定的值每一次查找都会导致被查找的结点* 变成根结点并且其他结点的位置深度基本上下降一半** param key 关键字* return 返回key对应的值*/public V search(K key) {TreeNodeK, V target searchHelper(key);return target null ? null : target.value;}/*** 从某个结点开始展开具体的展开规则是* 1node.parent root node.parent.left node* 那么将node.parent直接右旋这样node将会成为根节点* 2node.parent root node.parent.right node* 那么将node.parent直接左旋这样node将会成为根节点* 3node.parent ! rootnode.parent node.parent.left* node node.parent.right那么将node.parent.parent双向右旋* 4node.parent ! rootnode.parent node.parent.right* node node.parent.left那么将node.parent.parent双向左旋* 5node.parent ! rootnode.parent node.parent.left* node node.parent.left那么将node.parent.parent单向右旋* 然后将node.parent单向右旋* 6node.parent ! rootnode.parent node.parent.right* node node.parent.right那么将node.parent.parent单向左旋* 然后将node.parent单向左旋** param node 待旋转的结点*/private void splaying(TreeNodeK, V node) {while (node.parent ! null) {if (node.parent root) {if (node.parent.left node) {// 情况1singleRightRotate(node.parent);} else {// 情况2singleLeftRotate(node.parent);}} else if (node.parent node.parent.parent.left) {if (node node.parent.right) {// 情况3doubleRightRotate(node.parent.parent);} else {// 情况5singleRightRotate(node.parent.parent);singleRightRotate(node.parent);}} else {if (node node.parent.right) {// 情况6singleLeftRotate(node.parent.parent);singleLeftRotate(node.parent);} else {// 情况4doubleLeftRotate(node.parent.parent);}}}}/*** 搜索SplayTree中具有指定关键字的结点** param key 关键字* return 返回关键字和key相等的结点如果不存在返回null*/private TreeNodeK, V searchHelper(K key) {TreeNodeK, V cur root;while (cur ! null) {int cmp cur.key.compareTo(key);if (cmp 0) {cur cur.right;} else if (cmp 0) {cur cur.left;} else {break;}}// 可能从break跳出也可能完全没进入while循环if (cur ! null) {splaying(cur);}return cur;}/*** 伸展树的结点类型** param K 关键字类型* param V 值类型*/private static class TreeNodeK extends ComparableK, V {public K key;public V value;public TreeNodeK, V left;public TreeNodeK, V right;public TreeNodeK, V parent;public TreeNode(K key, V value) {this.key key;this.value value;}public void setParent(TreeNodeK, V parent) {this.parent parent;}}public static void main(String[] args) {SplayTreeInteger, Integer splayTree new SplayTree();splayTree.insert(1, 1);splayTree.insert(32, 32);splayTree.insert(30, 30);splayTree.insert(31, 31);splayTree.insert(28, 28);splayTree.insert(29, 29);splayTree.insert(26, 26);splayTree.insert(27, 27);splayTree.insert(24, 24);splayTree.insert(25, 25);splayTree.insert(22, 22);splayTree.insert(23, 23);splayTree.insert(20, 20);splayTree.insert(21, 21);splayTree.insert(18, 18);splayTree.insert(19, 19);splayTree.insert(16, 16);splayTree.insert(17, 17);splayTree.insert(14, 14);splayTree.insert(15, 15);splayTree.insert(12, 12);splayTree.insert(13, 13);splayTree.insert(10, 10);splayTree.insert(11, 11);splayTree.insert(8, 8);splayTree.insert(9, 9);splayTree.insert(6, 6);splayTree.insert(7, 7);splayTree.insert(4, 4);splayTree.insert(5, 5);splayTree.insert(2, 2);splayTree.insert(3, 3);System.out.println(splayTree.preOrder());System.out.println(splayTree.inOrder());System.out.println(splayTree.search(2));System.out.println(splayTree.search(3));System.out.println(splayTree.search(4));System.out.println(splayTree.search(5));System.out.println(splayTree.search(6));System.out.println(splayTree.search(7));System.out.println(splayTree.search(8));System.out.println(splayTree.search(9));System.out.println(访问部分结点后遍历);System.out.println(splayTree.preOrder());System.out.println(splayTree.inOrder());}
}
