当前位置: 首页 > news >正文

网站被攻击如何处理购物链接

网站被攻击如何处理,购物链接,专业格泰网站建设,陆家网站建设目录 一、基本介绍 二、伸展操作 1. 左右情况的伸展 2. 左左情况的伸展 3. 右左情况的伸展 4. 右右情况的伸展 三、其它操作 1. 插入 2. 删除 四、代码实现 一、基本介绍 伸展树是一种二叉搜索树,伸展树也是一种平衡树,不过伸展树并不像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 SplayTree<K extends Comparable<K>, V> {private TreeNode<K, V> root;/*** 向伸展树中插入一个新的结点** @param key   关键字* @param value 值*/public void insert(K key, V value) {TreeNode<K, V> cur = root;TreeNode<K, 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;}}TreeNode<K, 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();}TreeNode<K, V> cur = root;while (cur != null) {if (cur.left != null) {TreeNode<K, 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();}TreeNode<K, V> cur = root;while (cur != null) {if (cur.left != null) {TreeNode<K, 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) {TreeNode<K, V> node = searchHelper(key);if (node == null) {return null;}// 找到node的左孩子的最大值TreeNode<K, 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 TreeNode<K, V> findMax(TreeNode<K, V> root) {while (root != null && root.right != null) {root = root.right;}return root;}/*** 单向右旋转** @param node 被旋转的结点*/private void singleRightRotate(TreeNode<K, V> node) {// 特别注意在旋转过程中更新结点的父亲指针,否则将会导致回溯// 过程中产生某些意外情况TreeNode<K, 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(TreeNode<K, V> node) {TreeNode<K, 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(TreeNode<K, V> node) {singleLeftRotate(node.left);singleRightRotate(node);}/*** 双向左旋转** @param node 被旋转的结点*/private void doubleLeftRotate(TreeNode<K, V> node) {singleRightRotate(node.right);singleLeftRotate(node);}/*** 根据关键字查找指定的值,每一次查找都会导致被查找的结点* 变成根结点,并且其他结点的位置深度基本上下降一半** @param key 关键字* @return 返回key对应的值*/public V search(K key) {TreeNode<K, V> target = searchHelper(key);return target == null ? null : target.value;}/*** 从某个结点开始展开,具体的展开规则是:* (1)node.parent == root && node.parent.left == node,* 那么将node.parent直接右旋,这样node将会成为根节点* (2)node.parent == root && node.parent.right == node,* 那么将node.parent直接左旋,这样node将会成为根节点* (3)node.parent != root,node.parent == node.parent.left* && node == node.parent.right,那么将node.parent.parent双向右旋* (4)node.parent != root,node.parent == node.parent.right* && node == node.parent.left,那么将node.parent.parent双向左旋* (5)node.parent != root,node.parent == node.parent.left* && node == node.parent.left,那么将node.parent.parent单向右旋,* 然后将node.parent单向右旋* (6)node.parent != root,node.parent == node.parent.right* && node == node.parent.right,那么将node.parent.parent单向左旋,* 然后将node.parent单向左旋** @param node 待旋转的结点*/private void splaying(TreeNode<K, V> node) {while (node.parent != null) {if (node.parent == root) {if (node.parent.left == node) {// 情况(1)singleRightRotate(node.parent);} else {// 情况(2)singleLeftRotate(node.parent);}} else if (node.parent == node.parent.parent.left) {if (node == node.parent.right) {// 情况(3)doubleRightRotate(node.parent.parent);} else {// 情况(5)singleRightRotate(node.parent.parent);singleRightRotate(node.parent);}} else {if (node == node.parent.right) {// 情况(6)singleLeftRotate(node.parent.parent);singleLeftRotate(node.parent);} else {// 情况(4)doubleLeftRotate(node.parent.parent);}}}}/*** 搜索SplayTree中具有指定关键字的结点** @param key 关键字* @return 返回关键字和key相等的结点,如果不存在,返回null*/private TreeNode<K, V> searchHelper(K key) {TreeNode<K, 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 TreeNode<K extends Comparable<K>, V> {public K key;public V value;public TreeNode<K, V> left;public TreeNode<K, V> right;public TreeNode<K, V> parent;public TreeNode(K key, V value) {this.key = key;this.value = value;}public void setParent(TreeNode<K, V> parent) {this.parent = parent;}}public static void main(String[] args) {SplayTree<Integer, 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());}
}

http://www.dt0577.cn/news/21711.html

相关文章:

  • 黄州做网站的windows优化大师兑换码
  • 网站空间 独立ip互联网舆情监控系统
  • html编辑器哪个软件好用搜索引擎优化排名关键字广告
  • 只做正品的购物网站免费培训课程
  • 简易网页广州网站seo推广
  • 广州网站建设高端网推广软件的渠道有哪些
  • 给企业做网站赚钱吗适合推广的app有哪些
  • 天台县低价网站建设优化大师的功能有哪些
  • 网站建设需求怎么写138ip查询网域名解析
  • 武汉高端网站建设网站搜什么关键词好
  • 网站的制作郑州网络推广服务
  • 徐州网站建设什么是seo技术
  • wordpress+仿简书seo怎么做优化工作
  • 吴江政府网站建设局什么软件可以搜索关键词精准
  • 做购物网站适合的服务器seo厂家电话
  • 个人接做网站多少钱百度推广app下载
  • 公司变更法人需要多少费用沈阳seo排名公司
  • 打赏网站开发免费代理浏览网页
  • 河源新闻头条最新新闻优化大师班级
  • 天津做网站品牌推广专员
  • 网站添加悬浮二维码站长工具使用方法
  • 中建八局第一建设有限公司中标游戏行业seo整站优化
  • 杭州市上城区建设局网站网站模板搭建
  • phpcms 还有人用吗怎样进行seo优化
  • seo投放营销桔子seo查询
  • 制作网站注册页面模板网站开发的流程
  • 网站母版页怎么做百度竞价电话
  • 四川省住房和城乡建设厅网站电话美发培训职业学校
  • 做企业网站收费多少钱网络宣传的方法渠道
  • 未来软件网站建设杭州谷歌seo公司