电脑知识|欧美黑人一区二区三区|软件|欧美黑人一级爽快片淫片高清|系统|欧美黑人狂野猛交老妇|数据库|服务器|编程开发|网络运营|知识问答|技术教程文章 - 好吧啦网

您的位置:首頁技術文章
文章詳情頁

Java數據結構與算法解析——伸展樹

瀏覽:31日期:2022-09-05 13:51:20
伸展樹簡介

伸展樹(Splay Tree)是特殊的二叉查找樹。

它的特殊是指,它除了本身是棵二叉查找樹之外,它還具備一個特點: 當某個節點被訪問時,伸展樹會通過旋轉使該節點成為樹根。這樣做的好處是,下次要訪問該節點時,能夠迅速的訪問到該節點。

特性

1.和普通的二叉查找樹相比,具有任何情況下、任何操作的平攤O(log2n)的復雜度,時間性能上更好

2.和一般的平衡二叉樹比如 紅黑樹、AVL樹相比,維護更少的節點額外信息,空間性能更優,同時編程復雜度更低

3.在很多情況下,對于查找操作,后面的查詢和之前的查詢有很大的相關性。這樣每次查詢操作將被查到的節點旋轉到樹的根節點位置,這樣下次查詢操作可以很快的完成

4.可以完成對區間的查詢、修改、刪除等操作,可以實現線段樹和樹狀數組的所有功能

旋轉

伸展樹實現O(log2n)量級的平攤復雜度依靠每次對伸展樹進行查詢、修改、刪除操作之后,都進行旋轉操作 Splay(x, root),該操作將節點x旋轉到樹的根部。

伸展樹的旋轉有六種類型,如果去掉鏡像的重復,則為三種:zig(zag)、zig-zig(zag-zag)、zig-zag(zag-zig)。

1 自底向上的方式進行旋轉

1.1 zig旋轉 Java數據結構與算法解析——伸展樹

如圖所示,x節點的父節點為y,x為y的左子節點,且y節點為根。則只需要對x節點進行一次右旋(zig操作),使之成為y的父節點,就可以使x成為伸展樹的根節點。

1.2 zig-zig旋轉 Java數據結構與算法解析——伸展樹

如上圖所示,x節點的父節點y,y的父節點z,三者在一字型鏈上。此時,先對y節點和z節點進行zig旋轉,然后再對x節點和y節點進行zig旋轉,最后變為右圖所示,x成為y和z的祖先節點。

1.3 zig-zag旋轉 Java數據結構與算法解析——伸展樹

如上圖所示,x節點的父節點y,y的父節點z,三者在之字型鏈上。此時,先對x節點和y節點進行zig旋轉,然后再對x節點和y節點進行zag旋轉,最后變為右圖所示,x成為y和z的祖先節點。

2 自頂向下的方式進行旋轉這種方式不需要節點存儲其父節點的引用。當我們沿著樹向下搜索某個節點x時,將搜索路徑上的節點及其子樹移走。構建兩棵臨時的樹——左樹和右樹。沒有被移走的節點構成的樹稱為中樹。

(1) 當前節點x是中樹的根

(2) 左樹L保存小于x的節點

(3) 右樹R保存大于x的節點

開始時候,x是樹T的根,左樹L和右樹R都為空。三種旋轉操作:

2.1 zig旋轉 Java數據結構與算法解析——伸展樹

如圖所示,x節點的子節點y就是我們要找的節點,則只需要對y節點進行一次右旋(zig操作),使之成為x的父節點,就可以使y成為伸展樹的根節點。將y作為中樹的根,同時,x節點移動到右樹R中,顯然右樹上的節點都大于所要查找的節點。

2.2 zig-zig旋轉 Java數據結構與算法解析——伸展樹 如上圖所示,x節點的左子節點y,y的左子節點z,三者在一字型鏈上,且要查找的節點位于z節點為根的子樹中。此時,對x節點和y節點進行zig,然后對z和y進行zig,使z成為中樹的根,同時將y及其子樹掛載到右樹R上。

2.3 zig-zag旋轉

Java數據結構與算法解析——伸展樹

如上圖所示,x節點的左子節點y,y的右子節點z,三者在之字型鏈上,且需要查找的元素位于以z為根的子樹上。此時,先對x節點和y節點進行zig旋轉,將x及其右子樹掛載到右樹R上,此時y成為中樹的根節點;然后再對z節點和y節點進行zag旋轉,使得z成為中樹的根節點。

2.4 合并 Java數據結構與算法解析——伸展樹

最后,找到節點或者遇到空節點之后,需要對左、中、右樹進行合并。如圖所示,將左樹掛載到中樹的最左下方(滿足遍歷順序要求),將右樹掛載到中樹的最右下方(滿足遍歷順序要求)。

伸展樹的實現 1.節點

public class SplayTree<T extends Comparable<T>> { private SplayTreeNode<T> mRoot; // 根結點 public class SplayTreeNode<T extends Comparable<T>> {T key;// 關鍵字(鍵值)SplayTreeNode<T> left; // 左孩子SplayTreeNode<T> right; // 右孩子public SplayTreeNode() { this.left = null; this.right = null;}public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) { this.key = key; this.left = left; this.right = right;} }}

SplayTree是伸展樹,而SplayTreeNode是伸展樹節點。在此,我將SplayTreeNode定義為SplayTree的內部類。在伸展樹SplayTree中包含了伸展樹的根節點mRoot。SplayTreeNode包括的幾個組成元素:

(1) key – 是關鍵字,是用來對伸展樹的節點進行排序的。

(2) left – 是左孩子。

(3) right – 是右孩子。

2.旋轉

/* * 旋轉key對應的節點為根節點,并返回根節點。 * * 注意: * (a):伸展樹中存在'鍵值為key的節點'。 * 將'鍵值為key的節點'旋轉為根節點。 * (b):伸展樹中不存在'鍵值為key的節點',并且key < tree.key。 * b-1 '鍵值為key的節點'的前驅節點存在的話,將'鍵值為key的節點'的前驅節點旋轉為根節點。 * b-2 '鍵值為key的節點'的前驅節點存在的話,則意味著,key比樹中任何鍵值都小,那么此時,將最小節點旋轉為根節點。 * (c):伸展樹中不存在'鍵值為key的節點',并且key > tree.key。 * c-1 '鍵值為key的節點'的后繼節點存在的話,將'鍵值為key的節點'的后繼節點旋轉為根節點。 * c-2 '鍵值為key的節點'的后繼節點不存在的話,則意味著,key比樹中任何鍵值都大,那么此時,將最大節點旋轉為根節點。 */ private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) {if (tree == null) return tree;SplayTreeNode<T> N = new SplayTreeNode<T>();SplayTreeNode<T> l = N;SplayTreeNode<T> r = N;SplayTreeNode<T> c;for (; ; ) { int cmp = key.compareTo(tree.key); if (cmp < 0) {if (key.compareTo(tree.left.key) < 0) { c = tree.left; /* rotate right */ tree.left = c.right; c.right = tree; tree = c; if (tree.left == null)break;}r.left = tree; /* link right */r = tree;tree = tree.left; } else if (cmp > 0) {if (tree.right == null) break;if (key.compareTo(tree.right.key) > 0) { c = tree.right; /* rotate left */ tree.right = c.left; c.left = tree; tree = c; if (tree.right == null)break;}l.right = tree; /* link left */l = tree;tree = tree.right; } else {break; }}l.right = tree.left;/* assemble */r.left = tree.right;tree.left = N.right;tree.right = N.left;return tree; } public void splay(T key) {mRoot = splay(mRoot, key); }}

上面的代碼的作用:將”鍵值為key的節點”旋轉為根節點,并返回根節點。它的處理情況共包括:

(a):伸展樹中存在”鍵值為key的節點”。

將”鍵值為key的節點”旋轉為根節點。

(b):伸展樹中不存在”鍵值為key的節點”,并且key < tree->key。

b-1) “鍵值為key的節點”的前驅節點存在的話,將”鍵值為key的節點”的前驅節點旋轉為根節點。

b-2) “鍵值為key的節點”的前驅節點存在的話,則意味著,key比樹中任何鍵值都小,那么此時,將最小節點旋轉為根節點。

(c):伸展樹中不存在”鍵值為key的節點”,并且key > tree->key。

c-1) “鍵值為key的節點”的后繼節點存在的話,將”鍵值為key的節點”的后繼節點旋轉為根節點。

c-2) “鍵值為key的節點”的后繼節點不存在的話,則意味著,key比樹中任何鍵值都大,那么此時,將最大節點旋轉為根節點。

下面列舉個例子分別對a進行說明。

在下面的伸展樹中查找10,,共包括”右旋” –> “右鏈接” –> “組合”這3步。

Java數據結構與算法解析——伸展樹

01, 右旋

對應代碼中的”rotate right”部分

Java數據結構與算法解析——伸展樹

02, 右鏈接

對應代碼中的”link right”部分

Java數據結構與算法解析——伸展樹

03.組合

對應代碼中的”assemble”部分

Java數據結構與算法解析——伸展樹

提示:如果在上面的伸展樹中查找”70”,則正好與”示例1”對稱,而對應的操作則分別是”rotate left”, “link left”和”assemble”。

其它的情況,例如”查找15是b-1的情況,查找5是b-2的情況”等等,這些都比較簡單,大家可以自己分析。

3.插入

/** * 將結點插入到伸展樹中,并返回根節點 * @param tree 伸展樹的根節點 * @param z 插入的結點 * @return */ private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) {int cmp;SplayTreeNode<T> y = null;SplayTreeNode<T> x = tree;// 查找z的插入位置while (x != null) { y = x; cmp = z.key.compareTo(x.key); if (cmp < 0)x = x.left; else if (cmp > 0)x = x.right; else {System.out.printf('不允許插入相同節點(%d)!n', z.key);z = null;return tree; }}if (y == null) tree = z;else { cmp = z.key.compareTo(y.key); if (cmp < 0)y.left = z; elsey.right = z;}return tree; } public void insert(T key) {SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null);// 如果新建結點失敗,則返回。if ((z = new SplayTreeNode<T>(key, null, null)) == null) return;// 插入節點mRoot = insert(mRoot, z);// 將節點(key)旋轉為根節點mRoot = splay(mRoot, key); }

insert(key)是提供給外部的接口,它的作用是新建節點(節點的鍵值為key),并將節點插入到伸展樹中;然后,將該節點旋轉為根節點。

insert(tree, z)是內部接口,它的作用是將節點z插入到tree中。insert(tree, z)在將z插入到tree中時,僅僅只將tree當作是一棵二叉查找樹,而且不允許插入相同節點。

4.刪除

/** * * @param tree 伸展樹 * @param key 刪除的結點 * @return */ private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) {SplayTreeNode<T> x;if (tree == null) return null;// 查找鍵值為key的節點,找不到的話直接返回。if (search(tree, key) == null) return tree;// 將key對應的節點旋轉為根節點。tree = splay(tree, key);if (tree.left != null) { // 將'tree的前驅節點'旋轉為根節點 x = splay(tree.left, key); // 移除tree節點 x.right = tree.right;}else x = tree.right;tree = null;return x; } public void remove(T key) {mRoot = remove(mRoot, key); }

remove(key)是外部接口,remove(tree, key)是內部接口。

remove(tree, key)的作用是:刪除伸展樹中鍵值為key的節點。

它會先在伸展樹中查找鍵值為key的節點。若沒有找到的話,則直接返回。若找到的話,則將該節點旋轉為根節點,然后再刪除該節點。

伸展樹實現完整代碼

public class SplayTree<T extends Comparable<T>> { private SplayTreeNode<T> mRoot; // 根結點 public class SplayTreeNode<T extends Comparable<T>> {T key;// 關鍵字(鍵值)SplayTreeNode<T> left; // 左孩子SplayTreeNode<T> right; // 右孩子public SplayTreeNode() { this.left = null; this.right = null;}public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) { this.key = key; this.left = left; this.right = right;} } /* * 旋轉key對應的節點為根節點,并返回根節點。 * * 注意: * (a):伸展樹中存在'鍵值為key的節點'。 * 將'鍵值為key的節點'旋轉為根節點。 * (b):伸展樹中不存在'鍵值為key的節點',并且key < tree.key。 * b-1 '鍵值為key的節點'的前驅節點存在的話,將'鍵值為key的節點'的前驅節點旋轉為根節點。 * b-2 '鍵值為key的節點'的前驅節點存在的話,則意味著,key比樹中任何鍵值都小,那么此時,將最小節點旋轉為根節點。 * (c):伸展樹中不存在'鍵值為key的節點',并且key > tree.key。 * c-1 '鍵值為key的節點'的后繼節點存在的話,將'鍵值為key的節點'的后繼節點旋轉為根節點。 * c-2 '鍵值為key的節點'的后繼節點不存在的話,則意味著,key比樹中任何鍵值都大,那么此時,將最大節點旋轉為根節點。 */ private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) {if (tree == null) return tree;SplayTreeNode<T> N = new SplayTreeNode<T>();SplayTreeNode<T> l = N;SplayTreeNode<T> r = N;SplayTreeNode<T> c;for (; ; ) { int cmp = key.compareTo(tree.key); if (cmp < 0) {if (key.compareTo(tree.left.key) < 0) { c = tree.left; /* rotate right */ tree.left = c.right; c.right = tree; tree = c; if (tree.left == null)break;}r.left = tree; /* link right */r = tree;tree = tree.left; } else if (cmp > 0) {if (tree.right == null) break;if (key.compareTo(tree.right.key) > 0) { c = tree.right; /* rotate left */ tree.right = c.left; c.left = tree; tree = c; if (tree.right == null)break;}l.right = tree; /* link left */l = tree;tree = tree.right; } else {break; }}l.right = tree.left;/* assemble */r.left = tree.right;tree.left = N.right;tree.right = N.left;return tree; } public void splay(T key) {mRoot = splay(mRoot, key); } /** * 將結點插入到伸展樹中,并返回根節點 * @param tree 伸展樹的根節點 * @param z 插入的結點 * @return */ private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) {int cmp;SplayTreeNode<T> y = null;SplayTreeNode<T> x = tree;// 查找z的插入位置while (x != null) { y = x; cmp = z.key.compareTo(x.key); if (cmp < 0)x = x.left; else if (cmp > 0)x = x.right; else {System.out.printf('不允許插入相同節點(%d)!n', z.key);z = null;return tree; }}if (y == null) tree = z;else { cmp = z.key.compareTo(y.key); if (cmp < 0)y.left = z; elsey.right = z;}return tree; } public void insert(T key) {SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null);// 如果新建結點失敗,則返回。if ((z = new SplayTreeNode<T>(key, null, null)) == null) return;// 插入節點mRoot = insert(mRoot, z);// 將節點(key)旋轉為根節點mRoot = splay(mRoot, key); } /* * 刪除結點(z),并返回被刪除的結點 * * 參數說明: * bst 伸展樹 * z 刪除的結點 */ /** * * @param tree 伸展樹 * @param key 刪除的結點 * @return */ private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) {SplayTreeNode<T> x;if (tree == null) return null;// 查找鍵值為key的節點,找不到的話直接返回。if (search(tree, key) == null) return tree;// 將key對應的節點旋轉為根節點。tree = splay(tree, key);if (tree.left != null) { // 將'tree的前驅節點'旋轉為根節點 x = splay(tree.left, key); // 移除tree節點 x.right = tree.right;}else x = tree.right;tree = null;return x; } public void remove(T key) {mRoot = remove(mRoot, key); } /* * (遞歸實現)查找'伸展樹x'中鍵值為key的節點 */ private SplayTreeNode<T> search(SplayTreeNode<T> x, T key) {if (x==null) return x;int cmp = key.compareTo(x.key);if (cmp < 0) return search(x.left, key);else if (cmp > 0) return search(x.right, key);else return x; } public SplayTreeNode<T> search(T key) {return search(mRoot, key); } /* * 查找最小結點:返回tree為根結點的伸展樹的最小結點。 */ private SplayTreeNode<T> minimum(SplayTreeNode<T> tree) {if (tree == null) return null;while(tree.left != null) tree = tree.left;return tree; } public T minimum() {SplayTreeNode<T> p = minimum(mRoot);if (p != null) return p.key;return null; } /* * 查找最大結點:返回tree為根結點的伸展樹的最大結點。 */ private SplayTreeNode<T> maximum(SplayTreeNode<T> tree) {if (tree == null) return null;while(tree.right != null) tree = tree.right;return tree; } public T maximum() {SplayTreeNode<T> p = maximum(mRoot);if (p != null) return p.key;return null; }}

來自:http://blog.csdn.net/u012124438/article/details/78067998

標簽: Java
相關文章:
主站蜘蛛池模板: 北京康百特科技有限公司-分子蒸馏-短程分子蒸馏设备-实验室分子蒸馏设备 | 不锈钢管件(不锈钢弯头,不锈钢三通,不锈钢大小头),不锈钢法兰「厂家」-浙江志通管阀 | NMRV减速机|铝合金减速机|蜗轮蜗杆减速机|NMRV减速机厂家-东莞市台机减速机有限公司 | 电位器_轻触开关_USB连接器_广东精密龙电子科技有限公司 | 飞象网 - 通信人每天必上的网站 全球化工设备网—化工设备,化工机械,制药设备,环保设备的专业网络市场。 | 火锅底料批发-串串香技术培训[川禾川调官网]| 气动隔膜泵-电动隔膜泵-循环热水泵-液下排污/螺杆/管道/化工泵「厂家」浙江绿邦 | 服务器之家 - 专注于服务器技术及软件下载分享 | 球磨机,节能球磨机价格,水泥球磨机厂家,粉煤灰球磨机-吉宏机械制造有限公司 | 便携式谷丙转氨酶检测仪|华图生物科技百科 | 老城街小面官网_正宗重庆小面加盟技术培训_特色面馆加盟|牛肉拉面|招商加盟代理费用多少钱 | 化妆品加工厂-化妆品加工-化妆品代加工-面膜加工-广东欧泉生化科技有限公司 | 防锈油-助焊剂-光学玻璃清洗剂-贝塔防锈油生产厂家 | 伊卡洛斯软装首页-电动窗帘,别墅窗帘,定制窗帘,江浙沪1000+别墅窗帘案例 | 加热制冷恒温循环器-加热制冷循环油浴-杭州庚雨仪器有限公司 | 广东之窗网| 空心明胶胶囊|植物胶囊|清真胶囊|浙江绿键胶囊有限公司欢迎您! | 软文发布平台 - 云软媒网络软文直编发布营销推广平台 | 衬塑管道_衬四氟管道厂家-淄博恒固化工设备有限公司 | 英国雷迪地下管线探测仪-雷迪RD8100管线仪-多功能数字听漏仪-北京迪瑞进创科技有限公司 | 青岛侦探调查_青岛侦探事务所_青岛调查事务所_青岛婚外情取证-青岛狄仁杰国际侦探公司 | 聚合氯化铝厂家-聚合氯化铝铁价格-河南洁康环保科技 | 过滤器_自清洗过滤器_气体过滤器_苏州华凯过滤技术有限公司 | 钢结构厂房造价_钢结构厂房预算_轻钢结构厂房_山东三维钢结构公司 | 权威废金属|废塑料|废纸|废铜|废钢价格|再生资源回收行情报价中心-中废网 | 二手光谱仪维修-德国OBLF光谱仪|进口斯派克光谱仪-热电ARL光谱仪-意大利GNR光谱仪-永晖检测 | 搪玻璃冷凝器_厂家-越宏化工设备 | 背压阀|减压器|不锈钢减压器|减压阀|卫生级背压阀|单向阀|背压阀厂家-上海沃原自控阀门有限公司 本安接线盒-本安电路用接线盒-本安分线盒-矿用电话接线盒-JHH生产厂家-宁波龙亿电子科技有限公司 | 多物理场仿真软件_电磁仿真软件_EDA多物理场仿真软件 - 裕兴木兰 | 山西3A认证|太原AAA信用认证|投标AAA信用证书-山西AAA企业信用评级网 | 手机存放柜,超市储物柜,电子储物柜,自动寄存柜,行李寄存柜,自动存包柜,条码存包柜-上海天琪实业有限公司 | 登车桥动力单元-非标液压泵站-非标液压系统-深圳市三好科技有限公司 | 山东PE给水管厂家,山东双壁波纹管,山东钢带增强波纹管,山东PE穿线管,山东PE农田灌溉管,山东MPP电力保护套管-山东德诺塑业有限公司 | 无缝钢管-聊城无缝钢管-小口径无缝钢管-大口径无缝钢管 - 聊城宽达钢管有限公司 | 集装箱箱号识别_自重载重图像识别_铁路车号自动识别_OCR图像识别 | 甲级防雷检测仪-乙级防雷检测仪厂家-上海胜绪电气有限公司 | 酶联免疫分析仪-多管旋涡混合仪|混合器-莱普特科学仪器(北京)有限公司 | 实验室隔膜泵-无油防腐蚀隔膜泵-耐腐蚀隔膜真空泵-杭州景程仪器 电杆荷载挠度测试仪-电杆荷载位移-管桩测试仪-北京绿野创能机电设备有限公司 | 工业rfid读写器_RFID工业读写器_工业rfid设备厂商-ANDEAWELL | 次氯酸钠厂家,涉水级次氯酸钠,三氯化铁生产厂家-淄博吉灿化工 | 哈希PC1R1A,哈希CA9300,哈希SC4500-上海鑫嵩实业有限公司 |