每天5分鐘用C#學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)（31）查找 Part 2

前面討論的幾種查找方法中，二分查找效率最高，但其要求表中記錄按照關(guān)鍵字有序，且只能在順序表上實現(xiàn)，從而需要在插入和刪除操作時移動很多的元素。如果不希望表中記錄按關(guān)鍵字有序，而又希望得到較高的插入和刪除效率，可以考慮使用幾種特殊的二叉樹或樹作為表的組織形式。本篇閱讀時間大約為15min。

1二叉查找樹

基本概念

二叉查找樹（Binary Search Tree, BST）又稱二叉排序樹，它是滿足如下性質(zhì)的二叉樹：

若它的左子樹非空，則左子樹上所有記錄的值均小于根記錄的值；

若它的右子樹非空，則右子樹上所有記錄的值均大于根記錄的值；

左、右子樹又各是一棵二叉查找樹。

假如有一個序列{62,88,58,47,35,73,51,99,37,93}，那么構(gòu)造出來的二叉查找樹如下圖所示：

二叉查找樹是遞歸定義的，其一般理解是：二叉查找樹中任一節(jié)點，其值為k，只要該節(jié)點有左孩子，則左孩子的值必小于k，只要有右孩子，則右孩子的值必大于k。二叉查找樹的一個重要的性質(zhì)是：中序遍歷該樹得到的序列是一個遞增有序的序列。

代碼實現(xiàn)

有關(guān)二叉查找樹的新增和刪除節(jié)點如何實現(xiàn)，可以閱讀我的《每天5分鐘用C#學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之二叉樹》一節(jié)，該文使用C#實現(xiàn)了二叉查找樹。

需要注意的是：對于二叉查找樹最糟糕的情況是插入一個有序序列，使得具有N個元素的集合生成了高度為N的單枝二叉樹，從而使其退化了一個單鏈表，其查找效率也會會由O(logn)變?yōu)镺(n)。

2平衡二叉樹

剛剛提到在二叉查找樹中，如果插入元素的順序接近有序，那么二叉查找樹將退化為鏈表，從而導(dǎo)致二叉查找樹的查找效率大大降低。前蘇聯(lián)兩位科學(xué)家G.M. Adelson-Velskii和E.M. Landis在1962年的一篇論文中提出了一種自平衡二叉查找樹。這種二叉查找樹在插入和刪除操作中，可以通過一系列的旋轉(zhuǎn)操作來保持平衡，從而保證了二叉查找樹的查找效率。最終這種二叉查找樹被命名為AVL-Tree，也被稱為平衡二叉樹。

基本概念

平衡二叉樹定義(AVL)：它或者是一顆空樹，或者具有以下性質(zhì)的二叉樹：它的左子樹和右子樹的深度之差的絕對值不超過1，且它的左子樹和右子樹都是一顆平衡二叉樹。

平衡因子(BF)：結(jié)點的左子樹的深度減去右子樹的深度，那么顯然-1<=bf<=1;

平衡二叉樹上所有結(jié)點的平衡因子只可能是-1、0和1。只要二叉樹上有一個結(jié)點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。

基本操作

假設(shè)我們已經(jīng)有棵平衡二叉樹，現(xiàn)在讓我們來看看插入節(jié)點后，原來節(jié)點失去平衡后，平衡二叉樹會進行不同類型（RR、LL、LR以及RL）的旋轉(zhuǎn)來保持平衡。

SortedDictionary類

另一種與平衡二叉樹類似的是紅黑樹，紅黑樹和AVL樹的區(qū)別在于它使用顏色來標識節(jié)點的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴格的平衡。在.NET BCL中的System.Collections.Generic命名空間下，SortedDictionary類就是使用紅黑樹實現(xiàn)的。紅黑樹和AVL樹的原理非常接近，但是復(fù)雜度卻遠勝于AVL樹，這里也就不做討論。博客園里也已經(jīng)有了不少關(guān)于紅黑樹的比較好的介紹的文章，有興趣的可以去閱讀閱讀。

在代碼中，我們可以模擬100000個數(shù)字進行添加：

Random random =newRandom();intarray_count =100000;List intList =newList();for(inti =0; i <= array_count; i++){intran = random.Next();? ? intList.Add(ran);}SortedDictionary dic_int =newSortedDictionary();foreach(variteminintList){if(dic_int.ContainsKey(item) ==false)? ? {? ? ? ? dic_int.Add(item, item);? ? }}

當然，還可以與SortedList（SortedList內(nèi)部是Array，而SortedDictionary內(nèi)部是紅黑樹）進行一下對比，這里使用了老趙的CodeTimer類：

（1）新增操作對比：

由于SortedList用Array數(shù)組保存，每次進行插入操作時，首先用二分查找法找到相應(yīng)的位置，得到位置以后，SortedList會把該位置以后的值依次往后移一個位置，空出當前位，再把值插入，這個過程中用到了Array.Copy方法，而調(diào)用該方法是比較損耗性能的，具體代碼如下：

privatevoid? Insert(int? index, TKey key, TValue value){? ? ......if(index

SortedDictionary在添加操作時，只會根據(jù)紅黑樹的特性，旋轉(zhuǎn)節(jié)點，保持平衡，并沒有對Array.Copy的調(diào)用。下面我們就用數(shù)據(jù)測試一下：循環(huán)一個int型、容量為10w的隨機數(shù)組，分別用SortedList和SortedDictionary添加，看看效率如何：

staticvoidSortedAddInTest(){Random random =newRandom();intarray_count =100000;List intList =newList();for(inti =0; i <= array_count; i++)? ? {intran = random.Next();? ? ? ? intList.Add(ran);? ? }SortedList sortedlist_int =newSortedList();SortedDictionary dic_int =newSortedDictionary();CodeTimer.Time("sortedList_Add_int",1, () =>? ? {foreach(variteminintList)? ? ? ? {if(sortedlist_int.ContainsKey(item) ==false)sortedlist_int.Add(item,"test"+ item.ToString());? ? ? ? }? ? });CodeTimer.Time("sortedDictionary_Add_int",1, () =>? ? {foreach(variteminintList)? ? ? ? {if(dic_int.ContainsKey(item) ==false)dic_int.Add(item,"test"+ item.ToString());? ? ? ? }? ? });}

運行結(jié)果如下圖所示：

從上圖可以看出：在大量添加操作的情況下，SortedDictionary性能（無論是從時間消耗、CPU計算、還是GC垃圾回收次數(shù)）優(yōu)于SortedList。

（2）查找操作對比：

兩者的查詢操作中，時間復(fù)雜度都為O(logn)，且源碼中也沒有額外的操作造成性能損失，那么他們在查詢操作中性能如何？繼續(xù)上面一個例子進行測試。

staticvoidSortedQueryInTest(){Random random =newRandom();intarray_count =100000;List intList =newList();for(inti =0; i <= array_count; i++)? ? {intran = random.Next();? ? ? ? intList.Add(ran);? ? }SortedList sortedlist_int =newSortedList();SortedDictionary dic_int =newSortedDictionary();foreach(variteminintList)? ? {if(sortedlist_int.ContainsKey(item) ==false)sortedlist_int.Add(item,"test"+ item.ToString());? ? }foreach(variteminintList)? ? {if(dic_int.ContainsKey(item) ==false)dic_int.Add(item,"test"+ item.ToString());? ? }CodeTimer.Time("sortedList_Search_int",1, () =>? ? {foreach(variteminintList)? ? ? ? {? ? ? ? ? ? sortedlist_int.ContainsKey(item);? ? ? ? }? ? });CodeTimer.Time("sortedDictionary_Search_int",1, () =>? ? {foreach(variteminintList)? ? ? ? {? ? ? ? ? ? dic_int.ContainsKey(item);? ? ? ? }? ? });}

運行結(jié)果如下圖所示：

從上圖可以看出：兩者在循環(huán)10w次的情況下，查詢操作SortedList大概為SortedDictionary的一半，這是由于SortedList已經(jīng)在插入操作時已經(jīng)將其轉(zhuǎn)化為了一個有序的數(shù)組，從而在查詢時可以直接使用二分查找提高效率。SortedDictionary則是一個二叉排序樹，查詢效率理論上也是O(logn)，但其較有序數(shù)組的二分查找效率還是差了一點點。

（3）刪除操作對比：

從添加操作例子可以看出，由于SortedList內(nèi)部使用Array數(shù)組進行存儲數(shù)據(jù)，而數(shù)組本身的局限性使得SortedList大部分的添加操作都要調(diào)用Array.Copy方法，從而導(dǎo)致了性能的損失，這種情況同樣存在于刪除操作中。

SortedList每次刪除操作都會將刪除位置后的值往前挪動一位，以填補刪除位置的空白，這個過程剛好跟添加操作反過來，同樣也需要調(diào)用Array.Copy方法，相關(guān)代碼如下：

publicvoid RemoveAt(int index){? ? ......if(index

而SortedDictionary使用紅黑樹結(jié)構(gòu)存儲元素，紅黑樹本身是一棵二叉查找樹，它的刪除和二叉查找樹的刪除類似。首先要找到真正的刪除點，當被刪除結(jié)點n存在左右孩子時，真正的刪除點應(yīng)該是n的中序遍歷的前驅(qū)，關(guān)于這一點請參考二叉查找樹的刪除。如下圖所示，當刪除結(jié)點20時，實際被刪除的結(jié)點應(yīng)該為18，結(jié)點20的數(shù)據(jù)變?yōu)?8。

這里，我們?nèi)匀贿x擇上面的例子來進行一個簡單的對比測試，仍然是10w個元素的數(shù)據(jù)量：

staticvoidSortedDeleteInTest(){Random random =newRandom();intarray_count =100000;List intList =newList();for(inti =0; i <= array_count; i++)? ? {intran = random.Next();? ? ? ? intList.Add(ran);? ? }SortedList sortedlist_int =newSortedList();SortedDictionary dic_int =newSortedDictionary();foreach(variteminintList)? ? {if(sortedlist_int.ContainsKey(item) ==false)sortedlist_int.Add(item,"test"+ item.ToString());? ? }foreach(variteminintList)? ? {if(dic_int.ContainsKey(item) ==false)dic_int.Add(item,"test"+ item.ToString());? ? }CodeTimer.Time("sortedList_Delete_String",1, () =>? ? {foreach(variteminintList)? ? ? ? {? ? ? ? ? ? sortedlist_int.Remove(item);? ? ? ? }? ? });CodeTimer.Time("sortedDictionary_Delete_String",1, () =>? ? {foreach(variteminintList)? ? ? ? {? ? ? ? ? ? dic_int.Remove(item);? ? ? ? }? ? });}

運行結(jié)果如下圖所示：

從上圖也可以看出：在10w次的刪除操作中，SortedDictionary的處理速度和性能消耗較SortedList好的不是一丁半點。

（4）對比總結(jié)：

① SortedList用數(shù)組存儲數(shù)據(jù)，所以對GC比較友好一點，而且對于相對比較有序的輸入源而言，操作較少（eg:List intList = Enumerable.Range(0, array_count).ToList()）。

② SortedDictionary用節(jié)點鏈存儲數(shù)據(jù)，所以對GC而言，相對比較復(fù)雜。所以當可以預(yù)見到集合中的元素比較少的時候或者數(shù)據(jù)本身相對比較有序時，應(yīng)該傾向于使用SortedList。

3小結(jié)

本篇介紹了查找算法中查找樹算法部分的兩個算法：二叉查找樹和平衡二叉樹，然后還對比了.NET BCL中的兩個類SortedDictionary和SortedList。

下一篇，我們繼續(xù)看看另外的查找方法：哈希表和Hashtable。

4參考資料

程杰，《大話數(shù)據(jù)結(jié)構(gòu)》

陳廣，《數(shù)據(jù)結(jié)構(gòu)（C#語言描述）》

段恩澤，《數(shù)據(jù)結(jié)構(gòu)（C#語言版）》

許兩會，《.NET集合類的研究-有序集合》

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容