程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 伸展樹(Splay樹)的簡要操作,伸展splay樹

伸展樹(Splay樹)的簡要操作,伸展splay樹

編輯:C++入門知識

伸展樹(Splay樹)的簡要操作,伸展splay樹


  伸展樹(splay樹),是二叉排序樹的一種。【兩個月之前寫過,今天突然想寫個博客。。。】

  伸展樹和一般的二叉排序樹不同的是,在每次執行完插入、查詢、刪除等操作後,都會自動平衡這棵樹。(說是自動,也就是多了一段代碼,把這個節點提到根節點的位置上罷了)

  伸展樹的調整是基於兩種旋轉操作的【左旋右旋嘛】。

  分別是這樣的(對2號節點操作):

  

  

  (有點草率啊這個圖)

  對於這兩個操作,只需要處理好指針為空的情況即可(我的splay樹包含了father指針,可能比另一種寫法更繁瑣一些)

  

1 void lec(nod x) 2 { 3 nod y=x->fa; 4 y->rs=x->ls; 5 if (x->ls!=NULL) 6 x->ls->fa=y; 7 x->ls=y; 8 x->fa=y->fa; 9 if (y->fa!=NULL) 10 { 11 if (y==y->fa->ls) 12 y->fa->ls=x; 13 else 14 y->fa->rs=x; 15 } 16 y->fa=x; 17 } 18 19 void ric(nod x) 20 { 21 nod y=x->fa; 22 y->ls=x->rs; 23 if (x->rs!=NULL) 24 x->rs->fa=y; 25 x->rs=y; 26 x->fa=y->fa; 27 if (y->fa!=NULL) 28 { 29 if (y==y->fa->ls) 30 y->fa->ls=x; 31 else 32 y->fa->rs=x; 33 } 34 y->fa=x; 35 } 左旋右旋

  這樣的話,我們就可以怼出一個splay操作,每次把一個操作節點上移到根節點位置。

1 void splay(nod x) 2 { 3 nod y; 4 while (x->fa!=NULL) 5 { 6 y=x->fa; 7 if (y->fa==NULL) 8 { 9 if (y->ls==x) 10 ric(x); 11 else 12 lec(x); 13 break; 14 } 15 if (x==y->ls) 16 { 17 if (y==y->fa->ls) 18 ric(y),ric(x); 19 else 20 ric(x),lec(x); 21 } 22 else 23 { 24 if (y==y->fa->ls) 25 lec(x),ric(x); 26 else 27 lec(y),lec(x); 28 } 29 } 30 s=x; 31 } splay操作

  然後只要在每次插入、查找等操作後,加上一句splay(當前結點指針)就好了。。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved