日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無(wú)先后，達(dá)者為師

網(wǎng)站首頁(yè) 編程語(yǔ)言 正文

C#實(shí)現(xiàn)二叉查找樹(shù)_C#教程

作者：Ruby_Lu ? 更新時(shí)間： 2022-06-16 編程語(yǔ)言

對(duì)于符號(hào)表，要支持高效的插入操作，就需要一種鏈?zhǔn)浇Y(jié)構(gòu)。但單鏈表無(wú)法使用二分查找，因?yàn)槎植檎业母咝?lái)自于能夠快速通過(guò)索引取得任何子數(shù)組的中間元素，鏈表只能遍歷（詳細(xì)描述）。為了將二分查找的效率和鏈表的靈活性結(jié)合，需要更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)：二叉查找樹(shù)。具體來(lái)說(shuō)，就是使用每個(gè)結(jié)點(diǎn)含有兩個(gè)鏈接的二叉查找樹(shù)來(lái)高效地實(shí)現(xiàn)符號(hào)表。

一棵二叉查找樹(shù)（BST）是一棵二叉樹(shù)，其中每個(gè)結(jié)點(diǎn)都含有一個(gè)IComparable 類(lèi)型的鍵以及相關(guān)聯(lián)的值，且每個(gè)結(jié)點(diǎn)的鍵都大于其左子樹(shù)的任意結(jié)點(diǎn)的鍵而小于右子樹(shù)的任意結(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;//二叉樹(shù)根節(jié)點(diǎn)

        /// <summary>
        /// 嵌套定義一個(gè)私有類(lèi)表示二叉查找樹(shù)上的一個(gè)結(jié)點(diǎn)。
        /// 每個(gè)結(jié)點(diǎn)都含有一個(gè)鍵，一個(gè)值，一條左連接，一條右連接和一個(gè)結(jié)點(diǎn)計(jì)數(shù)器。
        /// 變量 N 給出了以該結(jié)點(diǎn)為根的子樹(shù)的結(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;
        }
}

一棵二叉查找樹(shù)代表了一組鍵（及其相應(yīng)的值）的集合，而一個(gè)可以用多棵不同的二叉查找樹(shù)表（起始根結(jié)點(diǎn)不同，樹(shù)就不同），下面是一種情況。但不管什么情況的樹(shù)，我們將一棵二叉查找樹(shù)的所有鍵投影到一條直線(xiàn)上，一定可以得到一條有序的鍵列。

2.查找

在符號(hào)表中查找一個(gè)鍵可能有兩種結(jié)果：命中和未命中。下面的實(shí)現(xiàn)算法是在二叉查找樹(shù)中查找一個(gè)鍵的遞歸算法：如果樹(shù)是空的，則查找未命中，如果被查找的鍵和根結(jié)點(diǎn)的鍵相等，查找命中，否則就遞歸地在適當(dāng)?shù)刈訕?shù)中繼續(xù)查找。如果被查找的鍵較小就選擇左子樹(shù)，較大則選擇右子樹(shù)。當(dāng)找到一個(gè)含有被查找鍵的結(jié)點(diǎn)（命中）或者當(dāng)前子樹(shù)變?yōu)榭眨ㄎ疵校r(shí)這個(gè)過(guò)程才結(jié)束。

public override Value Get(Key key)
        {
            return Get(root,key);
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="x">第一個(gè)參數(shù)是結(jié)點(diǎn)（子樹(shù)的根結(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è)不存在于樹(shù)中的結(jié)點(diǎn)并結(jié)束于一條空連接時(shí)，需要將連接指向一個(gè)含有被查找的鍵的新節(jié)點(diǎn)。下面插入方法的邏輯：如果樹(shù)是空的，就返回一個(gè)含有該鍵值對(duì)的新結(jié)點(diǎn)賦值給這個(gè)空連接；如果被查找的鍵小于根結(jié)點(diǎn)的鍵，繼續(xù)在左子樹(shù)中插入該鍵，否則就在右子樹(shù)中插入。并且需要更新計(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)用前的代碼想象成沿著樹(shù)向下走，將遞歸調(diào)用后的代碼想象成沿著樹(shù)向上爬。對(duì)于 Get 方法，這對(duì)應(yīng)著一系列的返回指令。對(duì)于 Put 方法，意味著重置搜索路徑上每個(gè)父結(jié)點(diǎn)指向子結(jié)點(diǎn)的連接，并增加路徑上每個(gè)結(jié)點(diǎn)中計(jì)數(shù)器的值。在一棵簡(jiǎn)單的二叉查找樹(shù)中，唯一的新連接就是在最底層指向新結(jié)點(diǎn)的連接，重置更上層的連接可以通過(guò)比較語(yǔ)句來(lái)避免。

4.分析

二叉查找樹(shù)上算法的運(yùn)行時(shí)間取決于樹(shù)的形狀，而樹(shù)的形狀又取決于鍵的插入順序。在最好情況下，一棵含有 N 個(gè)結(jié)點(diǎn)的樹(shù)是完全平衡的，每條空連接和根結(jié)點(diǎn)的距離都是 ~lgN 。在最壞情況下，搜索路徑上有 N 個(gè)結(jié)點(diǎn)。

對(duì)于隨機(jī)模型的分析而言，二叉查找樹(shù)和快速排序很相似。根結(jié)點(diǎn)就是快速排序中的第一個(gè)切分元素，對(duì)于其他子樹(shù)也同樣使用。

在由 N 個(gè)隨機(jī)鍵構(gòu)造的二叉查找樹(shù)，查找命中的平均所需的比較次數(shù)為 ~2lnN （約1.39lgN），插入和查找未命中平均所需的比較次數(shù)也為~2lnN （約1.39lgN）。插入和查找未命中比查找命中需要一次額外比較。

由此可知，在二叉查找樹(shù)中查找比二分查找的成本高出約 39% ，但是插入操作所需的成本達(dá)到了對(duì)數(shù)界別。

有序性相關(guān)的方法和刪除操作

1.最大鍵和最小鍵

如果根結(jié)點(diǎn)的左連接為空，那么一棵二叉查找樹(shù)中最小的鍵就是根結(jié)點(diǎn)；如果左連接非空，那么樹(shù)中的最小鍵就是左子樹(shù)中的最小鍵。

        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 小于二叉查找樹(shù)的根結(jié)點(diǎn)的鍵，那么小于等于 key 的最大鍵 Floor( key ) 一定在根結(jié)點(diǎn)的左子樹(shù)中；如果給定的鍵大于二叉查找樹(shù)的根結(jié)點(diǎn)，那么只有當(dāng)根節(jié)點(diǎn)的右子樹(shù)中存在小于等于給定鍵的結(jié)點(diǎn)時(shí)，小于等于給定鍵的最大鍵才會(huì)出現(xiàn)在右子樹(shù)中，否則根結(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è)诙娌檎覙?shù)的每個(gè)結(jié)點(diǎn)中維護(hù)的子樹(shù)結(jié)點(diǎn)計(jì)數(shù)器變量 N 就是用來(lái)支持此操作的。

如果要找到排名為 k 的鍵（即樹(shù)中正好有 k 個(gè)小于它的鍵）。如果左子樹(shù)中的結(jié)點(diǎn)樹(shù) t 大于 k，就繼續(xù)（遞歸地）在左子樹(shù)中查找排名為 k 的鍵；如果 t == k，就返回根結(jié)點(diǎn)的鍵；如果 t 小于 k，就遞歸地在右子樹(shù)中查找排名為 （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 類(lèi)似：如果給定的鍵等于根根結(jié)點(diǎn)的鍵，就返回左子樹(shù)中的節(jié)點(diǎn)數(shù) t ；如果給定的鍵小于根結(jié)點(diǎn)，就返回該鍵在左子樹(shù)中的排名（遞歸計(jì)算）；如果給定的鍵大于根結(jié)點(diǎn)，就返回 t+1 (根結(jié)點(diǎn)）再加上它在右子樹(shù)中的排名（遞歸計(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ù)中最難實(shí)現(xiàn)的就是刪除操作，我們先實(shí)現(xiàn)刪除最小鍵的操作。我們要不斷深入根節(jié)點(diǎn)的左子樹(shù)直到遇到一個(gè)空連接，然后將指向該結(jié)點(diǎn)的連接指向該結(jié)點(diǎn)的右子樹(shù)（只需在 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.刪除操作

我們 可以使用上面類(lèi)似的方法刪除任意只有一個(gè)子結(jié)點(diǎn)或者沒(méi)有子結(jié)點(diǎn)的結(jié)點(diǎn)，但是無(wú)法實(shí)現(xiàn)刪除有兩個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)的方法。我們?cè)趧h除 x 結(jié)點(diǎn)后用它的右子樹(shù)最小結(jié)點(diǎn)結(jié)點(diǎn)填補(bǔ)它的位置，這樣就可以保證樹(shù)的有序性，分四步完成：

  • 1.將指向即將被刪除的結(jié)點(diǎn)的連接保存為 t ;
  • 2.將 x 指向它的后繼結(jié)點(diǎn) Min（t.right）；
  • 3.將 x 的右鏈接指向 DeleteMin（t.right），也就是刪除右子樹(shù)最小連接，然后返回 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è)問(wèn)題，在選擇后繼結(jié)點(diǎn)應(yīng)該是隨機(jī)的，應(yīng)該考慮樹(shù)的對(duì)成性。

7.范圍查找

要實(shí)現(xiàn)能夠返回給定范圍內(nèi)鍵的方法 Keys（），需要一個(gè)遍歷二叉查找樹(shù)的基本方法，叫做中序遍歷。先找出根結(jié)點(diǎn)的左子樹(shù)中的符合的所有鍵，然后找出根結(jié)點(diǎn)的鍵，最后找出根結(jié)點(diǎn)右子樹(shù)的符合的所有鍵。

        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;//二叉樹(shù)根節(jié)點(diǎn)

        /// <summary>
        /// 嵌套定義一個(gè)私有類(lèi)表示二叉查找樹(shù)上的一個(gè)結(jié)點(diǎn)。
        /// 每個(gè)結(jié)點(diǎn)都含有一個(gè)鍵，一個(gè)值，一條左連接，一條右連接和一個(gè)結(jié)點(diǎn)計(jì)數(shù)器。
        /// 變量 N 給出了以該結(jié)點(diǎn)為根的子樹(shù)的結(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)（子樹(shù)的根結(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.性能分析

給定一棵樹(shù)，樹(shù)的高度決定了所有操作在最壞情況下的性能（范圍查找除外，因?yàn)樗念~外成本和返回的鍵的數(shù)量成正比），成正比。

隨機(jī)構(gòu)造的二叉查找樹(shù)的平均高度為樹(shù)中結(jié)點(diǎn)數(shù)量的對(duì)數(shù)級(jí)別，約為 2.99 lgN 。但如果構(gòu)造樹(shù)的鍵不是隨機(jī)的（例如，順序或者倒序），性能會(huì)大大降低，后面會(huì)講到平衡二叉查找樹(shù)。

算法 最壞情況下運(yùn)行時(shí)間的增長(zhǎng)量級(jí) 平均情況下的運(yùn)行時(shí)間的增長(zhǎng)量級(jí) 是否支持有序性相關(guān)操作
查找 插入 查找命中 插入
順序查找（無(wú)序鏈表） N N N/2 N 否
二分查找（有序數(shù)組） lgN N lgN N/2 是
二叉樹(shù)查找 N N 1.39lgN 1.39lgN 是

原文鏈接：https://www.cnblogs.com/afei-24/p/13525974.html

欄目分類(lèi)
最近更新