C#實(shí)現(xiàn)二叉查找樹
對(duì)于符號(hào)表，要支持高效的插入操作，就需要一種鏈?zhǔn)浇Y(jié)構(gòu)。但單鏈表無法使用二分查找，因?yàn)槎植檎业母咝碜杂谀軌蚩焖偻ㄟ^索引取得任何子數(shù)組的中間元素，鏈表只能遍歷（詳細(xì)描述）。為了將二分查找的效率和鏈表的靈活性結(jié)合，需要更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)：二叉查找樹。具體來說，就是使用每個(gè)結(jié)點(diǎn)含有兩個(gè)鏈接的二叉查找樹來高效地實(shí)現(xiàn)符號(hào)表。
一棵二叉查找樹（BST）是一棵二叉樹，其中每個(gè)結(jié)點(diǎn)都含有一個(gè)IComparable 類型的鍵以及相關(guān)聯(lián)的值，且每個(gè)結(jié)點(diǎn)的鍵都大于其左子樹的任意結(jié)點(diǎn)的鍵而小于右子樹的任意結(jié)點(diǎn)的鍵。
1.實(shí)現(xiàn)API
1.數(shù)據(jù)結(jié)構(gòu)
public class BinarySearchTreesST<Key, Value> : BaseSymbolTables<Key, Value>
where Key : IComparable
{
private Node root;//二叉樹根節(jié)點(diǎn)
/// <summary>
/// 嵌套定義一個(gè)私有類表示二叉查找樹上的一個(gè)結(jié)點(diǎn)。
/// 每個(gè)結(jié)點(diǎn)都含有一個(gè)鍵，一個(gè)值，一條左連接，一條右連接和一個(gè)結(jié)點(diǎn)計(jì)數(shù)器。
/// 變量 N 給出了以該結(jié)點(diǎn)為根的子樹的結(jié)點(diǎn)總數(shù)。
/// x.N = Size(x.left) + Size(x.right) + 1;
/// </summary>
private class Node
{
public Key key;
public Value value;
public Node left, right;
public int N;
public Node(Key key,Value value,int N)
{
this.key = key;
this.value = value;
this.N = N;
}
}
public override int Size()
{
return Size(root);
}
private int Size(Node x)
{
if (x == null)
return 0;
else
return x.N;
}
}一棵二叉查找樹代表了一組鍵（及其相應(yīng)的值）的集合，而一個(gè)可以用多棵不同的二叉查找樹表（起始根結(jié)點(diǎn)不同，樹就不同），下面是一種情況。但不管什么情況的樹，我們將一棵二叉查找樹的所有鍵投影到一條直線上，一定可以得到一條有序的鍵列。
2.查找
在符號(hào)表中查找一個(gè)鍵可能有兩種結(jié)果：命中和未命中。下面的實(shí)現(xiàn)算法是在二叉查找樹中查找一個(gè)鍵的遞歸算法：如果樹是空的，則查找未命中，如果被查找的鍵和根結(jié)點(diǎn)的鍵相等，查找命中，否則就遞歸地在適當(dāng)?shù)刈訕渲欣^續(xù)查找。如果被查找的鍵較小就選擇左子樹，較大則選擇右子樹。當(dāng)找到一個(gè)含有被查找鍵的結(jié)點(diǎn)（命中）或者當(dāng)前子樹變?yōu)榭眨ㄎ疵校r(shí)這個(gè)過程才結(jié)束。
public override Value Get(Key key)
{
return Get(root,key);
}
/// <summary>
///
/// </summary>
/// <param name="x">第一個(gè)參數(shù)是結(jié)點(diǎn)（子樹的根結(jié)點(diǎn)）</param>
/// <param name="key">第二個(gè)參數(shù)是被查找的鍵</param>
/// <returns></returns>
private Value Get(Node x, Key key)
{
if (x == null)
return default(Value);
int cmp = key.CompareTo(x.key);
if (cmp < 0)
return Get(x.left, key);
else if (cmp > 0)
return Get(x.right, key);
else
return x.value;
}
3.插入
插入方法和查找的實(shí)現(xiàn)差不多，當(dāng)查找一個(gè)不存在于樹中的結(jié)點(diǎn)并結(jié)束于一條空連接時(shí)，需要將連接指向一個(gè)含有被查找的鍵的新節(jié)點(diǎn)。下面插入方法的邏輯：如果樹是空的，就返回一個(gè)含有該鍵值對(duì)的新結(jié)點(diǎn)賦值給這個(gè)空連接；如果被查找的鍵小于根結(jié)點(diǎn)的鍵，繼續(xù)在左子樹中插入該鍵，否則就在右子樹中插入。并且需要更新計(jì)數(shù)器。
public override void Put(Key key, Value value)
{
root = Put(root,key,value);
}
private Node Put(Node x, Key key, Value value)
{
if (x == null)
return new Node(key,value,1);
int cmp = key.CompareTo(x.key);
if (cmp < 0)
x.left = Put(x.left, key, value); //注意 x.left = 的意思
else if (cmp > 0)
x.right = Put(x.right, key, value);//注意 x.right =
else
x.value = value;
x.N = Size(x.left) + Size(x.right) + 1;
return x;
}
在查找和插入的遞歸實(shí)現(xiàn)中，可以將遞歸調(diào)用前的代碼想象成沿著樹向下走，將遞歸調(diào)用后的代碼想象成沿著樹向上爬。對(duì)于 Get 方法，這對(duì)應(yīng)著一系列的返回指令。對(duì)于 Put 方法，意味著重置搜索路徑上每個(gè)父結(jié)點(diǎn)指向子結(jié)點(diǎn)的連接，并增加路徑上每個(gè)結(jié)點(diǎn)中計(jì)數(shù)器的值。在一棵簡(jiǎn)單的二叉查找樹中，唯一的新連接就是在最底層指向新結(jié)點(diǎn)的連接，重置更上層的連接可以通過比較語(yǔ)句來避免。
4.分析
二叉查找樹上算法的運(yùn)行時(shí)間取決于樹的形狀，而樹的形狀又取決于鍵的插入順序。在最好情況下，一棵含有 N 個(gè)結(jié)點(diǎn)的樹是完全平衡的，每條空連接和根結(jié)點(diǎn)的距離都是 ~lgN 。在最壞情況下，搜索路徑上有 N 個(gè)結(jié)點(diǎn)。
對(duì)于隨機(jī)模型的分析而言，二叉查找樹和快速排序很相似。根結(jié)點(diǎn)就是快速排序中的第一個(gè)切分元素，對(duì)于其他子樹也同樣使用。
在由 N 個(gè)隨機(jī)鍵構(gòu)造的二叉查找樹，查找命中的平均所需的比較次數(shù)為 ~2lnN （約1.39lgN），插入和查找未命中平均所需的比較次數(shù)也為~2lnN （約1.39lgN）。插入和查找未命中比查找命中需要一次額外比較。
由此可知，在二叉查找樹中查找比二分查找的成本高出約 39% ，但是插入操作所需的成本達(dá)到了對(duì)數(shù)界別。
有序性相關(guān)的方法和刪除操作
1.最大鍵和最小鍵
如果根結(jié)點(diǎn)的左連接為空，那么一棵二叉查找樹中最小的鍵就是根結(jié)點(diǎn)；如果左連接非空，那么樹中的最小鍵就是左子樹中的最小鍵。
public override Key Min()
{
return Min(root).key;
}
private Node Min(Node x)
{
if (x.left == null)
return x;
return Min(x.left);
}2.向上取整和向下取整
如果給定的鍵 key 小于二叉查找樹的根結(jié)點(diǎn)的鍵，那么小于等于 key 的最大鍵 Floor( key ) 一定在根結(jié)點(diǎn)的左子樹中；如果給定的鍵大于二叉查找樹的根結(jié)點(diǎn)，那么只有當(dāng)根節(jié)點(diǎn)的右子樹中存在小于等于給定鍵的結(jié)點(diǎn)時(shí)，小于等于給定鍵的最大鍵才會(huì)出現(xiàn)在右子樹中，否則根結(jié)點(diǎn)就是小于等于 key 的最大鍵。
/// <summary>
/// 向下取整
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public override Key Floor(Key key)
{
Node x = Floor(root,key);
if (x == null)
return default(Key);
return x.key;
}
private Node Floor(Node x, Key key)
{
if (x == null)
return default(Node);
int cmp = key.CompareTo(x.key);
if (cmp == 0)
return x;
if (cmp < 0)
return Floor(x.left,key);
Node t = Floor(x.right,key);
if (t != null)
return t;
else
return x;
}3.選擇操作
我們?cè)诙娌檎覙涞拿總€(gè)結(jié)點(diǎn)中維護(hù)的子樹結(jié)點(diǎn)計(jì)數(shù)器變量 N 就是用來支持此操作的。
如果要找到排名為 k 的鍵（即樹中正好有 k 個(gè)小于它的鍵）。如果左子樹中的結(jié)點(diǎn)樹 t 大于 k，就繼續(xù)（遞歸地）在左子樹中查找排名為 k 的鍵；如果 t == k，就返回根結(jié)點(diǎn)的鍵；如果 t 小于 k，就遞歸地在右子樹中查找排名為 （k-t-1）的鍵。
public override Key Select(int k)
{
return Select(root, k).key;
}
private Node Select(Node x, int k)
{
if (x == null)
return default(Node);
int t = Size(x.left);
if (t > k)
return Select(x.left, k);
else if (t < k)
return Select(x.right, k - t - 1);
else
return x;
}4.排名
排名是選擇操作的逆方法，它會(huì)返回給定鍵的排名。它的實(shí)現(xiàn)和 Select 類似：如果給定的鍵等于根根結(jié)點(diǎn)的鍵，就返回左子樹中的節(jié)點(diǎn)數(shù) t ；如果給定的鍵小于根結(jié)點(diǎn)，就返回該鍵在左子樹中的排名（遞歸計(jì)算）；如果給定的鍵大于根結(jié)點(diǎn)，就返回 t+1 (根結(jié)點(diǎn)）再加上它在右子樹中的排名（遞歸計(jì)算）。
public override int Rank(Key key)
{
return Rank(key,root);
}
private int Rank(Key key, Node x)
{
if (x == null)
return 0;
int cmp = key.CompareTo(x.key);
if (cmp < 0)
return Rank(key, x.left);
else if (cmp > 0)
return 1 + Size(x.left) + Rank(key, x.right);
else
return Size(x.left);
}5.刪除最大鍵和刪除最小鍵
二叉查找樹中最難實(shí)現(xiàn)的就是刪除操作，我們先實(shí)現(xiàn)刪除最小鍵的操作。我們要不斷深入根節(jié)點(diǎn)的左子樹直到遇到一個(gè)空連接，然后將指向該結(jié)點(diǎn)的連接指向該結(jié)點(diǎn)的右子樹（只需在 x.left == null 時(shí)返回右鏈接，賦值給上層的左連接）。
/// <summary>
/// 注意可考慮刪除根結(jié)點(diǎn)
/// </summary>
public override void DeleteMin()
{
root = DeleteMin(root);
}
private Node DeleteMin(Node x)
{
if (x.left == null)
return x.right;
x.left = DeleteMin(x.left);
x.N = Size(x.left) + Size(x.right) + 1;
return x;
}6.刪除操作
我們 可以使用上面類似的方法刪除任意只有一個(gè)子結(jié)點(diǎn)或者沒有子結(jié)點(diǎn)的結(jié)點(diǎn)，但是無法實(shí)現(xiàn)刪除有兩個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)的方法。我們?cè)趧h除 x 結(jié)點(diǎn)后用它的右子樹最小結(jié)點(diǎn)結(jié)點(diǎn)填補(bǔ)它的位置，這樣就可以保證樹的有序性，分四步完成：
- 1.將指向即將被刪除的結(jié)點(diǎn)的連接保存為 t ;
- 2.將 x 指向它的后繼結(jié)點(diǎn) Min（t.right）；
- 3.將 x 的右鏈接指向 DeleteMin（t.right），也就是刪除右子樹最小連接，然后返回 t 的右鏈接；
- 4.將 x 的左連接設(shè)為 t.left；
public override void Delete(Key key)
{
root = Delete(root,key);
}
private Node Delete(Node x, Key key)
{
if (x == null)
return null;
int cmp = key.CompareTo(x.key);
if (cmp < 0)
x.left = Delete(x.left, key);
else if (cmp > 0)
x.right = Delete(x.right, key);
else
{
if (x.right == null)
return x.left;
if (x.left == null)
return x.right;
Node t = x;
x = Min(t.right);
x.right = DeleteMin(t.right);
x.left = t.left;
}
x.N = Size(x.left) + Size(x.right) + 1;
return x;
}該算法有個(gè)問題，在選擇后繼結(jié)點(diǎn)應(yīng)該是隨機(jī)的，應(yīng)該考慮樹的對(duì)成性。
7.范圍查找
要實(shí)現(xiàn)能夠返回給定范圍內(nèi)鍵的方法 Keys（），需要一個(gè)遍歷二叉查找樹的基本方法，叫做中序遍歷。先找出根結(jié)點(diǎn)的左子樹中的符合的所有鍵，然后找出根結(jié)點(diǎn)的鍵，最后找出根結(jié)點(diǎn)右子樹的符合的所有鍵。
public override IEnumerable<Key> Keys(Key lo, Key hi)
{
Queue<Key> quene = new Queue<Key>();
Keys(root, quene,lo,hi);
return quene;
}
private void Keys(Node x, Queue<Key> quene, Key lo, Key hi)
{
if (x == null)
return;
int cmplo = lo.CompareTo(x.key);
int cmphi = hi.CompareTo(x.key);
if (cmplo < 0)
Keys(x.left,quene,lo,hi);
if (cmplo <= 0 && cmphi >= 0)
quene.Enqueue(x.key);
if (cmphi > 0)
Keys(x.right,quene,lo,hi);
}全部代碼
public class BinarySearchTreesST<Key, Value> : BaseSymbolTables<Key, Value>
where Key : IComparable
{
private Node root;//二叉樹根節(jié)點(diǎn)
/// <summary>
/// 嵌套定義一個(gè)私有類表示二叉查找樹上的一個(gè)結(jié)點(diǎn)。
/// 每個(gè)結(jié)點(diǎn)都含有一個(gè)鍵，一個(gè)值，一條左連接，一條右連接和一個(gè)結(jié)點(diǎn)計(jì)數(shù)器。
/// 變量 N 給出了以該結(jié)點(diǎn)為根的子樹的結(jié)點(diǎn)總數(shù)。
/// x.N = Size(x.left) + Size(x.right) + 1;
/// </summary>
private class Node
{
public Key key;
public Value value;
public Node left, right;
public int N;
public Node(Key key,Value value,int N)
{
this.key = key;
this.value = value;
this.N = N;
}
}
public override int Size()
{
return Size(root);
}
private int Size(Node x)
{
if (x == null)
return 0;
else
return x.N;
}
public override Value Get(Key key)
{
return Get(root,key);
}
/// <summary>
///
/// </summary>
/// <param name="x">第一個(gè)參數(shù)是結(jié)點(diǎn)（子樹的根結(jié)點(diǎn)）</param>
/// <param name="key">第二個(gè)參數(shù)是被查找的鍵</param>
/// <returns></returns>
private Value Get(Node x, Key key)
{
if (x == null)
return default(Value);
int cmp = key.CompareTo(x.key);
if (cmp < 0)
return Get(x.left, key);
else if (cmp > 0)
return Get(x.right, key);
else
return x.value;
}
public override void Put(Key key, Value value)
{
root = Put(root,key,value);
}
private Node Put(Node x, Key key, Value value)
{
if (x == null)
return new Node(key,value,1);
int cmp = key.CompareTo(x.key);
if (cmp < 0)
x.left = Put(x.left, key, value); //注意 x.left = 的意思
else if (cmp > 0)
x.right = Put(x.right, key, value);//注意 x.right =
else
x.value = value;
x.N = Size(x.left) + Size(x.right) + 1;
return x;
}
public override Key Min()
{
return Min(root).key;
}
private Node Min(Node x)
{
if (x.left == null)
return x;
return Min(x.left);
}
/// <summary>
/// 向下取整
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public override Key Floor(Key key)
{
Node x = Floor(root,key);
if (x == null)
return default(Key);
return x.key;
}
private Node Floor(Node x, Key key)
{
if (x == null)
return default(Node);
int cmp = key.CompareTo(x.key);
if (cmp == 0)
return x;
if (cmp < 0)
return Floor(x.left,key);
Node t = Floor(x.right,key);
if (t != null)
return t;
else
return x;
}
public override Key Select(int k)
{
return Select(root, k).key;
}
private Node Select(Node x, int k)
{
if (x == null)
return default(Node);
int t = Size(x.left);
if (t > k)
return Select(x.left, k);
else if (t < k)
return Select(x.right, k - t - 1);
else
return x;
}
public override int Rank(Key key)
{
return Rank(key,root);
}
private int Rank(Key key, Node x)
{
if (x == null)
return 0;
int cmp = key.CompareTo(x.key);
if (cmp < 0)
return Rank(key, x.left);
else if (cmp > 0)
return 1 + Size(x.left) + Rank(key, x.right);
else
return Size(x.left);
}
/// <summary>
/// 注意可考慮刪除根結(jié)點(diǎn)
/// </summary>
public override void DeleteMin()
{
root = DeleteMin(root);
}
private Node DeleteMin(Node x)
{
if (x.left == null)
return x.right;
x.left = DeleteMin(x.left);
x.N = Size(x.left) + Size(x.right) + 1;
return x;
}
public override void Delete(Key key)
{
root = Delete(root,key);
}
private Node Delete(Node x, Key key)
{
if (x == null)
return null;
int cmp = key.CompareTo(x.key);
if (cmp < 0)
x.left = Delete(x.left, key);
else if (cmp > 0)
x.right = Delete(x.right, key);
else
{
if (x.right == null)
return x.left;
if (x.left == null)
return x.right;
Node t = x;
x = Min(t.right);
x.right = DeleteMin(t.right);
x.left = t.left;
}
x.N = Size(x.left) + Size(x.right) + 1;
return x;
}
public override IEnumerable<Key> Keys(Key lo, Key hi)
{
Queue<Key> quene = new Queue<Key>();
Keys(root, quene,lo,hi);
return quene;
}
private void Keys(Node x, Queue<Key> quene, Key lo, Key hi)
{
if (x == null)
return;
int cmplo = lo.CompareTo(x.key);
int cmphi = hi.CompareTo(x.key);
if (cmplo < 0)
Keys(x.left,quene,lo,hi);
if (cmplo <= 0 && cmphi >= 0)
quene.Enqueue(x.key);
if (cmphi > 0)
Keys(x.right,quene,lo,hi);
}
}8.性能分析
給定一棵樹，樹的高度決定了所有操作在最壞情況下的性能（范圍查找除外，因?yàn)樗念~外成本和返回的鍵的數(shù)量成正比），成正比。
隨機(jī)構(gòu)造的二叉查找樹的平均高度為樹中結(jié)點(diǎn)數(shù)量的對(duì)數(shù)級(jí)別，約為 2.99 lgN 。但如果構(gòu)造樹的鍵不是隨機(jī)的（例如，順序或者倒序），性能會(huì)大大降低，后面會(huì)講到平衡二叉查找樹。
| 算法 | 最壞情況下運(yùn)行時(shí)間的增長(zhǎng)量級(jí) | 平均情況下的運(yùn)行時(shí)間的增長(zhǎng)量級(jí) | 是否支持有序性相關(guān)操作 | ||
| 查找 | 插入 | 查找命中 | 插入 | ||
| 順序查找（無序鏈表） | N | N | N/2 | N | 否 |
| 二分查找（有序數(shù)組） | lgN | N | lgN | N/2 | 是 |
| 二叉樹查找 | N | N | 1.39lgN | 1.39lgN | 是 |
到此這篇關(guān)于C#實(shí)現(xiàn)二叉查找樹的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了c#判斷正確的ip地址格式示例,需要的朋友可以參考下2014-02-02
.net中前臺(tái)javascript與后臺(tái)c#函數(shù)相互調(diào)用問題
.net中前臺(tái)javascript與后臺(tái)c#函數(shù)相互調(diào)用問題...2007-12-12
淺談C#單例模式的實(shí)現(xiàn)和性能對(duì)比
這篇文章主要介紹了淺談C#單例模式的實(shí)現(xiàn)和性能對(duì)比的相關(guān)資料,詳細(xì)的介紹了6種實(shí)現(xiàn)方式，需要的朋友可以參考下2017-09-09
C#難點(diǎn)逐個(gè)擊破（2）:out返回參數(shù)
之前提到ref是將原方法中的參數(shù)影響的結(jié)果返回到調(diào)用它的方法中，out與ref類似，相比之下，ref傳遞參數(shù)的地址，out是返回值。2010-02-02
模式匹配是一種高端的使用機(jī)制，它允許程序員在開發(fā)的時(shí)候以對(duì)象的類型作為條件篩選和分情況處理的一種手段，本文給大家介紹C#?模式匹配完全指南，感興趣的朋友跟隨小編一起看看吧2022-03-03
線程是操作系統(tǒng)分配CPU時(shí)間的基本單元，在一個(gè)進(jìn)程中可以有多個(gè)線程同時(shí)執(zhí)行代碼，這篇文章主要介紹了C#中多線程的使用Tread,需要的朋友可以參考下2022-10-10
這篇文章主要介紹了C#泛型類型知識(shí)，文中代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-06-06
C#中常使用進(jìn)度條的代碼...2007-03-03
c# WinForm制作圖片編輯工具(圖像拖動(dòng)、縮放、旋轉(zhuǎn)、摳圖)
這篇文章主要介紹了c# WinForm制作圖片編輯工具(可實(shí)現(xiàn)圖像拖動(dòng)、縮放、旋轉(zhuǎn)、摳圖)，幫助大家更好的理解和學(xué)習(xí)使用c#，感興趣的朋友可以了解下2021-03-03
C#內(nèi)置隊(duì)列類Queue用法實(shí)例
這篇文章主要介紹了C#內(nèi)置隊(duì)列類Queue用法,實(shí)例分析了C#內(nèi)置隊(duì)列的添加、移除等相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-04-04