小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

【查找結(jié)構(gòu) 2】二叉查找樹 [BST]

 靜聽沙漏 2012-01-08

當(dāng)所有的靜態(tài)查找結(jié)構(gòu)添加和刪除一個數(shù)據(jù)的時候，整個結(jié)構(gòu)都需要重建。這對于常常需要在查找過程中動態(tài)改變數(shù)據(jù)而言，是災(zāi)難性的。因此人們就必須去尋找高效的動態(tài)查找結(jié)構(gòu)，我們在這討論一個非常常用的動態(tài)查找樹——二叉查找樹。

二叉查找樹的特點(diǎn)

下面的圖就是兩棵二叉查找樹，我們可以總結(jié)一下他的特點(diǎn)：

(1) 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值

(2) 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值
(3) 它的左、右子樹也分別為二叉查找樹

 
 

我們中序遍歷這兩棵樹發(fā)現(xiàn)一個有序的數(shù)據(jù)序列： 【1 2 3 4 5 6 7 8 】

二叉查找樹的操作

插入操作：

現(xiàn)在我們要查找一個數(shù)9，如果不存在則，添加進(jìn)a圖。我們看看二叉查找樹動態(tài)添加的過程：

1). 數(shù)9和根節(jié)點(diǎn)4比較(9>4)，則9放在節(jié)點(diǎn)4的右子樹中。

2). 接著，9和節(jié)點(diǎn)5比較(9>5)，則9放在節(jié)點(diǎn)5的右子樹中。

3). 依次類推：直到9和節(jié)點(diǎn)8比較(9>8)，則9放在節(jié)點(diǎn)8的右子樹中，成為節(jié)點(diǎn)8的右孩子。

這個過程我們能夠發(fā)現(xiàn)，動態(tài)添加任何一個數(shù)據(jù)，都會加在原樹結(jié)構(gòu)的葉子節(jié)點(diǎn)上，而不會重新建樹。由此可見，動態(tài)查找結(jié)構(gòu)確實在這方面有巨大的優(yōu)勢。

刪除操作：

如果二叉查找樹中需要刪除的結(jié)點(diǎn)左、右子樹都存在，則刪除的時候需要改變一些子樹結(jié)構(gòu)，但所需要付出的代價很小。

具體的插入，刪除算法請參加《數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用——搜索樹》P5-8。[該章節(jié)已經(jīng)上傳到《查找結(jié)構(gòu)專題(6)：動態(tài)查找樹比較》中]。

二叉查找樹的效率分析

那么我們再來看看二叉查找樹的效率問題

很顯然，在a,b兩圖的二叉查找樹結(jié)構(gòu)中查找一個數(shù)據(jù)，并不需要遍歷全部的節(jié)點(diǎn)元素，查找效率確實提高了。但是有一個很嚴(yán)重的問題：我們在a圖中查找8需要比較5次數(shù)據(jù)，而在B圖中只需要比較3次。更為嚴(yán)重的是：如果按有序序列[1 2 3 4 5 6 7 8]建立一顆二叉查找樹，整棵樹就退化成了一個線性結(jié)構(gòu)（如c輸入圖：單支樹），此時查找8需要比較8次數(shù)據(jù)，和順序查找沒有什么不同。

總結(jié)一下：最壞情況下，構(gòu)成的二叉排序樹蛻變?yōu)閱沃洌瑯涞纳疃葹閚，其查找時間復(fù)雜度與順序查找一樣O(N)。最好的情況是二叉排序樹的形態(tài)和折半查找的判定樹相同，其平均查找長度和log2(N)成正比 （O(log2(n))）。

這說明：同樣一組數(shù)據(jù)集合，不同的添加順序會導(dǎo)致查找樹的結(jié)構(gòu)完全不一樣，直接影響了查找效率。

那么如何解決這個問題呢? 我們會在下面的專題中：《平衡二叉樹》中來解決。

下面是java實現(xiàn)的二叉查找樹（說句老實話，沒有指針的java實現(xiàn)數(shù)據(jù)結(jié)構(gòu)真是復(fù)雜）：

Java代碼
  1. package net.hr.algorithm.search;
  3. import java.util.ArrayList;
  5. /**
  6. * 二叉樹節(jié)點(diǎn)結(jié)構(gòu)
  7. * @author heartraid
  8. */
  9. class BSTNode<E extends Comparable<E>>{
  10. /**結(jié)點(diǎn)關(guān)鍵字*/
  11. E key=null;
  12. /**直接父親結(jié)點(diǎn)*/
  13. BSTNode<E> parent=null;
  14. /**結(jié)點(diǎn)左子樹的根節(jié)點(diǎn)*/
  15. BSTNode<E> lchild=null;
  16. /**結(jié)點(diǎn)右子樹的根節(jié)點(diǎn)*/
  17. BSTNode<E> rchild=null;
  19. BSTNode(E k){
  20. this.key=k;
  21. }
  23. }
  24. /**
  25. * 二叉查找樹 Binary Search Tree(BST)
  26. * @author heartraid
  27. *
  28. */
  29. public class BST<E extends Comparable<E>> {
  30. /**樹根*/
  31. private BSTNode<E> root=null;
  33. public BST(){
  34. }
  36. /**
  37. * BST 查詢關(guān)鍵字
  38. * @param key 關(guān)鍵字
  39. * @return 查詢成功/true, 查詢失敗/false
  40. */
  41. public boolean search(E key){
  42. System.out.print("搜索關(guān)鍵字["+key+"]：");
  43. if(key==null||root==null){
  44. System.out.println("搜索失敗");
  45. return false;
  46. }
  47. else{
  48. System.out.print("搜索路徑[");
  49. if(searchBST(root,key)==null){
  50. return false;
  51. }
  52. else return true;
  54. }
  55. }
  56. /**
  57. * BST插入關(guān)鍵字
  58. * @param key 關(guān)鍵字
  59. * @return 插入成功/true, 插入失敗/false
  60. */
  61. public boolean insert(E key){
  62. System.out.print("插入關(guān)鍵字["+key+"]：");
  63. if(key==null) return false;
  64. if(root==null){
  65. System.out.println("插入到樹根。");
  66. root=new BSTNode<E>(key);
  67. return true;
  68. }
  69. else{
  70. System.out.print("搜索路徑[");
  71. return insertBST(root,key);
  72. }
  73. }
  75. public boolean delete(E key){
  76. System.out.print("刪除關(guān)鍵字["+key+"]：");
  77. if(key==null||root==null){
  78. System.out.println("刪除失敗");
  79. return false;
  80. }
  81. else{
  82. System.out.print("搜索路徑[");
  84. //定位到樹中待刪除的結(jié)點(diǎn)
  85. BSTNode<E> nodeDel=searchBST(root,key);
  86. if(nodeDel==null){
  87. return false;
  88. }
  89. else{
  90. //nodeDel的右子樹為空,則只需要重接它的左子樹
  91. if(nodeDel.rchild==null){
  93. BSTNode<E> parent=nodeDel.parent;
  94. if(parent.lchild.key.compareTo(nodeDel.key)==0)
  95. parent.lchild=nodeDel.lchild;
  96. else
  97. parent.rchild=nodeDel.lchild;
  98. }
  99. //左子樹為空,則重接它的右子樹
  100. else if(nodeDel.lchild==null){
  101. BSTNode<E> parent=nodeDel.parent;
  102. if(parent.lchild.key.compareTo(nodeDel.key)==0)
  103. parent.lchild=nodeDel.rchild;
  104. else
  105. parent.rchild=nodeDel.rchild;
  106. }
  107. //左右子樹均不空
  108. else{
  109. BSTNode<E> q=nodeDel;
  110. //先找nodeDel的左結(jié)點(diǎn)s
  111. BSTNode<E> s=nodeDel.lchild;
  112. //然后再向s的右盡頭定位(這個結(jié)點(diǎn)將替代nodeDel)，其中q一直定位在s的直接父親結(jié)點(diǎn)
  113. while(s.rchild!=null){
  114. q=s;
  115. s=s.rchild;
  116. }
  117. //換掉nodeDel的關(guān)鍵字為s的關(guān)鍵字
  118. nodeDel.key=s.key;
  119. //重新設(shè)置s的左子樹
  120. if(q!=nodeDel)
  121. q.rchild=s.lchild;
  122. else
  123. q.lchild=s.lchild;
  124. }
  125. return true;
  126. }
  127. }
  128. }
  130. /**
  131. * 遞歸查找關(guān)鍵子
  132. * @param node 樹結(jié)點(diǎn)
  133. * @param key 關(guān)鍵字
  134. * @return 查找成功，返回該結(jié)點(diǎn)，否則返回null。
  135. */
  136. private BSTNode<E> searchBST(BSTNode<E> node, E key){
  137. if(node==null){
  138. System.out.println("]. 搜索失敗");
  139. return null;
  140. }
  141. System.out.print(node.key+" —>");
  142. //搜索到關(guān)鍵字
  143. if(node.key.compareTo(key)==0){
  144. System.out.println("]. 搜索成功");
  145. return node;
  146. }
  147. //在左子樹搜索
  148. else if(node.key.compareTo(key)>0){
  149. return searchBST(node.lchild,key);
  150. }
  151. //在右子樹搜索
  152. else{
  153. return searchBST(node.rchild,key);
  154. }
  155. }
  157. /**
  158. * 遞歸插入關(guān)鍵字
  159. * @param node 樹結(jié)點(diǎn)
  160. * @param key 樹關(guān)鍵字
  161. * @return true/插入成功，false/插入失敗
  162. */
  163. private boolean insertBST(BSTNode<E> node, E key){
  164. System.out.print(node.key+" —>");
  165. //在原樹中找到相同的關(guān)鍵字，無需插入。
  166. if(node.key.compareTo(key)==0)
  167. {
  168. System.out.println("]. 搜索有相同關(guān)鍵字，插入失敗");
  169. return false;
  170. }
  171. else{
  172. //搜索node的左子樹
  173. if(node.key.compareTo(key)>0){
  174. //如果當(dāng)前node的左子樹為空，則將新結(jié)點(diǎn)key node插入到左孩子處
  175. if(node.lchild==null) {
  176. System.out.println("]. 插入到"+node.key+"的左孩子");
  177. BSTNode<E> newNode=new BSTNode<E>(key);
  178. node.lchild=newNode;
  179. newNode.parent=node;
  180. return true;
  181. }
  182. //如果當(dāng)前node的左子樹存在，則繼續(xù)遞歸左子樹
  183. else return insertBST(node.lchild, key);
  184. }
  185. //搜索node的右子樹
  186. else{
  187. if(node.rchild==null){
  188. System.out.println("]. 插入到"+node.key+"的右孩子");
  189. BSTNode<E> newNode=new BSTNode<E>(key);
  190. node.rchild=newNode;
  191. newNode.parent=node;
  192. return true;
  193. }
  194. else return insertBST(node.rchild,key);
  195. }
  196. }
  198. }
  199. /**
  200. * 得到BST根節(jié)點(diǎn)
  201. * @return BST根節(jié)點(diǎn)f
  202. */
  203. public BSTNode<E> getRoot(){
  204. return this.root;
  205. }
  206. /**
  207. * 非遞歸中序遍歷BST
  208. */
  209. public void InOrderTraverse(){
  210. if(root==null)
  211. return;
  212. BSTNode<E> node=root;
  213. ArrayList<BSTNode<E>> stack=new ArrayList<BSTNode<E>>();
  214. stack.add(node);
  215. while(!stack.isEmpty()){
  216. while(node.lchild!=null){
  217. node=node.lchild;
  218. stack.add(node);
  219. }
  220. if(!stack.isEmpty()){
  221. BSTNode<E> topNode=stack.get(stack.size()-1);
  222. System.out.print(topNode.key+" ");
  223. stack.remove(stack.size()-1);
  224. if(topNode.rchild!=null){
  225. node=topNode.rchild;
  226. stack.add(node);
  227. }
  228. }
  229. }
  232. }
  234. /**
  235. * 測試
  236. */
  237. public static void main(String[] args) {
  238. BST<Integer> tree=new BST<Integer>();
  239. tree.insert(new Integer(100));
  240. tree.insert(new Integer(52));
  241. tree.insert(new Integer(166));
  242. tree.insert(new Integer(74));
  243. tree.insert(new Integer(11));
  244. tree.insert(new Integer(13));
  245. tree.insert(new Integer(66));
  246. tree.insert(new Integer(121));
  248. tree.search(new Integer(11));
  249. tree.InOrderTraverse();
  251. tree.delete(new Integer(11));
  252. tree.InOrderTraverse();
  254. }
  256. }
 

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多