C#實現平衡查詢樹

2022-04-15 19:00:16

之前講的二叉查詢樹在最壞情況下效能還是很低的。平衡查詢樹能夠保證無論如何構造它，它的執行時間都是對數級別。在一棵含有 N 個結點的樹中，我們希望樹高為 ~lgN，這樣我們就能保證所有查詢都能在 ~lgN 次比較內結束，就和二分查詢一樣。但是，在動態插入中保證樹的完美平衡的代價太高。我們稍微降低完美平衡的要求，學習一種能夠保證符號表 API 中所有操作均能在對數時間內完成的資料結構。

1. 2-3查詢樹

為了保證查詢樹的平衡性，我們需要一些靈活性，因此我們允許樹中的一個結點儲存多個鍵。一棵標準的二叉查詢樹中的結點稱為 2- 結點，含有一個鍵和兩條連線；將含有兩個鍵和三條連線的結點稱為 3- 結點（左連線指向的 2-3 樹中的鍵都小於該結點，中連線指向的 2-3 樹種中的鍵都位於該結點的兩個鍵之間，右連結指向的 2-3 樹中的鍵都大於該結點）。

一棵完美平衡的 2-3 查詢樹中的所有空連線到根結點的距離都應該事相同的。簡潔起見，這裡用 2-3 樹指代一棵完美平衡的 2-3 查詢樹（在其他情況下這個次表示一種更一般的結構）。

1.查詢

將二叉查詢樹的查詢演演算法一般化就能直接得到 2-3 樹的查詢演演算法。要判斷一個鍵是否存在樹中，先將它和根結點中的鍵比較。如果它和其中任意一個鍵相等，查詢命中；否則就根據比較的結果找到指向相應區間的連結，並在其指向的子樹中遞迴地繼續查詢。

2.向 2- 結點中插入新鍵

要在 2-3 樹中插入一個新結點，我們可以和二叉查詢樹一樣先進行一次未命中的查詢，然後把新結點掛在樹的底部。但這樣的話樹無法保持完美平衡性。我們使用 2-3 樹的主要原因就在於它能夠在插入後繼續保持平衡。

如果未命中的查詢結束於一個 2- 結點，處理就簡單：我們只要把這個 2- 結點替換成一個 3- 結點，將要插入的鍵儲存在其中即可。

但是，如果未命中的查詢結束於一個 3- 結點，就要麻煩一些。

3.向一棵只含有一個 3- 結點的樹中插入新鍵

在考慮一般情況之前，先假設我們需要向一棵只含有一個 3- 結點的樹中插入一個新鍵。這棵樹中有兩個鍵，所以它已經沒有可插入新鍵的空間了。為了將新鍵插入，我們先臨時將新鍵存入該結點，使之稱為一個 4- 結點（三個鍵和四條連結）。然後把這個 4- 結點轉換未一棵由 3個 2- 結點組成的 2-3 樹，其中一個結點（根）含有中鍵，一個結點含有3個鍵中的最小者（和根結點的左連線相連），一個結點含有3個鍵中的最大者。

這棵樹既是一棵含有3個結點的二叉查詢樹，同時也是一棵完美平衡的 2-3 樹，因為其中所有的空連結到根結點的距離都相等。插入樹前高度為 0，插入樹後高度為 1。

4.向一個父結點為 2- 結點的 3- 結點中插入新鍵

在這種情況下我們需要在維持樹的完美平衡下為新鍵騰出空間。先像上面一樣構造一個臨時的 4- 結點將其分解成3個 2- 結點，但此時我們不會為中鍵建立一個新結點，而是將其移至原父結點中。

5.向一個父結點為 3- 結點的 3- 結點插入新鍵

對於這種情況，我們還是構造一個臨時 4- 結點並將其分解，然後將它的中鍵插入它的父結點。但此時父結點也變成一個新的臨時 4- 結點，然後繼續在這個結點上進行相同的變換，直至遇到一個 2- 結點或到達根結點。

6.分解根結點

如果從插入結點到根結點都是 3- 結點，根結點最終變成一個臨時的 4- 結點。此時按照向一棵只有一個 3- 結點的樹中插入新鍵的方法，將臨時 4- 結點分解成3個 2- 結點，使得樹高加1。

7.區域性變換

將一個 4- 結點分解成一棵 2-3 樹可能有6種情況：

2-3 樹插入演演算法的根本在於這些變換都是區域性的：除了相關結點和連結之外不必修改或者檢查樹的其他部分。每次變換中，變更的連結樹不會超過一個很小的常數。

8.全域性性質

這些區域性變換不會影響樹的全域性有序性和平衡性：任意空連結到根結點的路徑長度都是相等的。和標準的二叉查詢樹由上向下生長不同， 2-3 樹的生長是由下向上的。

在一棵大小為 N 的 2-3 樹中，插入和查詢操作存取的結點必然不超過 lgN 個。因此可以確定 2-3 樹在最壞的情況下仍有較好的效能，任何查詢或者插入的成本都肯定不會超過對數級別。例如，含有 10億個結點的 2-3 樹的高度僅在 19到30之間。

但是，我們只是實現方式的一部分。儘管有可能編寫程式碼來對錶示2節點和3節點的不同資料型別執行轉換，但是我們已經描述的大多數任務在這種直接表示中都不方便實現。

2.紅黑二叉查詢樹

我們使用紅黑二叉查詢樹的簡單資料結構來表達並實現 2-3 樹。

1.定義

紅黑二元樹背後的基本思想是用標準的二叉查詢樹（完全由 2- 結點構成）和一些額外的資訊（替換 3- 結點）來表示 2-3 樹。我們將樹中的連結分為兩種型別：紅連結將兩個 2- 結點連結起來構成一個 3- 結點，黑連結則是 2-3 樹中的普通連結。我們將 3- 結點表示為一條左斜的紅色連結（兩個 2- 結點其中之一是另一個的左子結點）相連的兩個 2- 結點。這種表示法的一個優點是，無需修改就可以直接使用標準二叉查詢樹的 Get（）方法。

紅黑樹的另一種定義是含有紅黑連結並滿足下列條件的二叉查詢樹：

1.左連結均為左連結；
2.沒有任何一個結點同時和兩條紅連結相連；
3.該樹是完美黑色平衡的，即任意空連結到根結點的路徑上的黑連結數量相同。

滿足這樣定義的紅黑樹和相應的 2-3 樹是一一對應的。

2.一一對應

如果我們將一棵紅黑樹中的紅連結畫平，那麼所有的空連結到根結點的距離都是相同的。如果將有紅連結相連的結點合併，得到的就是一棵 2-3 樹。相反，如果將一棵 2-3 樹中的 3- 結點畫作由紅色連結相連的兩個 2- 結點，那麼不會存在能夠和兩條紅連結相連的結點，且樹必然是完美黑色平衡的，因為黑連結即 2-3 樹中的普通連結，根據定義這些連結必然是完美平衡的。無論我們用那種方式取定義它們，紅黑樹都既是二叉查詢樹，也是 2-3 樹。因此如果我們能夠在保持一一對應關係的基礎上實現 2-3 樹的插入演演算法，那麼我們就能將兩個演演算法的優點結合起來：二叉查詢樹中高效簡潔的查詢方法和 2-3 樹中高效的平衡插入演演算法。

3.顏色表示

因為每個結點都只會有一條指向自己的連結（從父結點指向它），我們將連結的顏色儲存在表示結點的 Node 資料型別的布林變數中。如果指向它的連結是紅色的，那麼該變數為 true，黑色則為 false。我們約定空連結為黑色。我們使用 IsRed（）來測試連結的顏色。

    public class RedBlackBST<Key, Value> : BaseSymbolTables<Key, Value>
        where Key : IComparable
    {
        private Node root;
        private  const bool RED = true;
        private const bool BLACK = false;
        private class Node
        {
            public Key key;
            public Value value;
            public Node left, right;
            public int N;
            public bool color;

            Node(Key key,Value value,int N, bool color)
            {
                this.key = key;
                this.value = value;
                this.N = N;
                this.color = color;
            }
        }

        private bool IsRed(Node x)
        {
            if (x == null)
            {
                return false;
            }
            return x.color == RED;
        }

        private int Size(Node x)
        {
            if (x == null)
                return 0;
            else
                return x.N;
        }
    }

4.旋轉

在我們實現的某些操作中可能會出現紅色右連結或者兩條連續的紅連結，但在操作完成前這些情況都會被小心地旋轉並修復。旋轉操作會改變紅連結的指向。

一條紅色的右連結被轉換為左連結，稱為左旋轉。它對應的方法接受一條指向紅黑樹中的某個結點的連結作為引數。假設被指向的結點的右連結是紅色的，這個方法會對樹進行必要的調整並返回一個指向包含同一組鍵的子樹且左連結為紅色的根結點的連結。其程式碼實現，只是將用兩個鍵中較小的作為根結點變成將較大的作為根結點。

        private Node RotateLeft(Node h)
        {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

        private Node RotateRight(Node h)
        {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

5.在旋轉後重置父結點的連結

無論是左旋轉還是右旋轉，旋轉操作都會返回一條連結。我們總是會用 RotateLeft 或 RotateRight 的返回值重置父結點或是根結點中相應的連結。返回的連結可能是左連結也可能是右連結，但是總會將它賦予父結點中的連結。這個連結可能是紅色也可能是黑色 --RotateLeft 和 RotateRight 都通過將x.color 設為 h.color 保留它原來的顏色。這種簡潔的程式碼是我們使用遞迴實現二叉查詢樹的各種方法的原因。

在插入新鍵時我們可以使用旋轉操作保證 2-3 樹和紅黑樹之間的一一對應，因為旋轉操作可以保持紅黑樹的兩個重要性質：有序性和完美平衡性。下面來看如何使用旋轉操作來保持紅黑樹的另外兩個重要性質：不存在兩條連續的紅連結和不存在紅色的右連結。

6.向單個 2- 結點中插入新鍵

一棵只含有一個鍵的紅黑樹只含有一個 2- 結點。插入另一個鍵後，需要馬上將它們旋轉。如果新鍵小於老鍵，只需新增一個紅色的結點即可。如果新鍵大於老鍵，那麼新增的紅色結點將會產生一條紅色的右連結，需要左旋轉將其旋轉為紅色左連線並修改根結點的連結，插入操作才算完成。兩種情況的結果均為一棵和單個 3- 結點等價的紅黑樹,其中含有兩個鍵，一條紅連結，樹的黑連結高度為 1。

7.向樹底部的 2- 結點插入新鍵

用和二叉查詢樹相同的方式向一棵紅黑樹中插入一個新鍵會在樹的底部新增一個結點（為了保證有序性），但總是用紅連結將新節點和它的父結點相連。

8.向一棵雙鍵樹（即一個 3- 結點）中插入新鍵

這種情況分為三種情況：新鍵小於樹中的兩個鍵，兩者之間，或是大於樹中的兩個鍵。每種情況都會產生一個同時連線兩條紅連結的結點，而我們的目的就是修正這一點：

總的來說，我們通過 0 次，1 次和 2 次旋轉以及顏色的變換得到了期望的結果。這些轉換是紅黑樹的動態變化的關鍵。

9.顏色變換

我們專門用一個方法 FlipColors 方法來轉換一個結點的兩個紅色子結點的顏色。除了將子結點的顏色由紅變黑之外，同時還要將父結點的顏色由黑變紅。這項操作最重要的性質在於它和旋轉操作一樣是區域性變換，不會影響整個樹的黑色平衡性。

        private void FlipColors(Node h)
        {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }

10.根結點總是黑色

根據前面的情況，顏色轉換會使根結點變為紅色。這也可能出現在很大的紅黑樹中。嚴格地說，紅色的根結點說明根結點是一個 3- 結點的一部分，但實際情況並不是。因此我們在每次插入後都會將根結點設定為黑色。當根結點由紅變黑時樹的高度就會加1。

11.向樹底部的 3- 結點插入新鍵

對於這種情況，前面的三種情況都會出現：可能是 3- 結點的右連結（只需要轉換顏色），或是左連結（需要右轉然後轉換顏色），或是中連結（需要左旋轉下層連結然後右旋轉上層連結，最後變換顏色）。顏色轉換會使中間結點變紅。

12.將紅連結在樹中向上傳遞

每次必要的旋轉之後都會進行顏色轉換，這使得中結點變紅。在父結點看來，處理這樣一個紅色的結點的方式和處理一個新插入的紅色結點完全相同，即繼續把紅連結轉移到中結點上去。下圖總結的三種情況顯示了在紅黑樹中實現 2-3 樹的插入演演算法的關鍵操作所需的步驟：要在一個 3- 結點下插入新鍵，先臨時建立一個 4- 結點，將其分解並將紅連結由中間鍵傳遞給它的父結點。重複這個過程，就能將紅連結在樹中向上傳遞，直至遇到一個 2- 結點或者根結點。

總之，只要慎重地使用左旋轉，右旋轉和顏色轉換三種操作，就能保證插入操作後紅黑樹和 2-3 樹的一一對應。在沿著插入結點到根結點的路徑向上移動時所經過的每個結點中順序完成以下操作，就能完成插入操作：

1.如果右子結點是紅色且左子結點是黑色，進行左旋轉；
2.如果左子結點和它的左子結點都是紅色，進行右轉；
3.如果左右子結點均為紅色，進行顏色轉換。

13.實現

因為保持樹的平衡性所需的操作是由下至上在每個經歷的結點中進行，所以實現很簡單：只需要在遞迴呼叫之後完成上面所說的三種操作，這裡通過三個 if 語句完成。

    public class RedBlackBST<Key, Value> : BaseSymbolTables<Key, Value>
        where Key : IComparable
    {
        private Node root;
        private  const bool RED = true;
        private const bool BLACK = false;
        private class Node
        {
            public Key key;
            public Value value;
            public Node left, right;
            public int N;
            public bool color;

            public Node(Key key,Value value,int N, bool color)
            {
                this.key = key;
                this.value = value;
                this.N = N;
                this.color = color;
            }
        }

        private bool IsRed(Node x)
        {
            if (x == null)
            {
                return false;
            }
            return x.color == RED;
        }

        private Node RotateLeft(Node h)
        {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

        private Node RotateRight(Node h)
        {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }
        private int Size(Node x)
        {
            if (x == null)
                return 0;
            else
                return x.N;
        }

        private void FlipColors(Node h)
        {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }

        public override void Put(Key key, Value value)
        {
            root = Put(root,key,value);
        }

        private Node Put(Node h, Key key, Value value)
        {
            if (h == null)
                return new Node(key,value,1,RED);

            int cmp = key.CompareTo(h.key);
            if (cmp < 0)
                h.left = Put(h.left, key, value);
            else if (cmp > 0)
                h.right = Put(h.right, key, value);
            else
                h.value = value;

            if (IsRed(h.right) && !IsRed(h.left))
                h = RotateLeft(h);
            if (IsRed(h.left) && IsRed(h.left.left))
                h = RotateRight(h);
            if (IsRed(h.left) && IsRed(h.right))
                FlipColors(h);

            h.N = Size(h.left) + Size(h.right) + 1;
            return h;
        }
    }

下圖時測試用例軌跡：

3.刪除操作

和插入操作一樣，我們也可以定義一系列區域性變換來在刪除一個結點的同時保持樹的完美平衡性。這個過程比較複雜，因為不僅要在為了刪除一個結點而構造臨時 4- 結點時沿著查詢路徑向下進行變換，還要分解遺留的 4- 結點時沿著查詢路徑向上進行變換。

1.自頂向下的 2-3-4 樹

開始之前，先學習一個沿著查詢路徑既能向上也能向下進行變換的簡單演演算法： 2-3-4 樹的插入演演算法，2-3-4 樹=中允許存在 4- 結點。它的插入演演算法沿查詢路徑向下變換是為了把凹徵當前結點不是 4- 結點（這樣樹底才有空間插入新的鍵），沿查詢路徑向上進行變換是為了將之前建立的 4- 結點配平。向下變換和 2-3 樹種分解 4- 結點所進行的變換相同。如果根結點是4-結點，就將它分解成3個 2- 結點，使得樹高加一。在向下查詢的過程中，如果遇到一個父結點是 2- 結點的 4- 結點，將 4- 結點分解成兩個 2- 結點並將中間鍵傳遞給父結點，使得父結點變成 3- 結點。如果遇到一個父結點是 3- 結點的 4- 結點，將 4- 結點分解成兩個 2- 結點並將中間鍵傳遞給父結點，使得父結點變為 4- 結點；不必擔心遇到父結點為 4- 結點的 4- 結點，因為插入演演算法本身就保證了這種情況不會出現。到達樹底之後，只會遇到 2- 結點或 3- 結點，所以我們可以插入新的鍵。

要用紅黑樹實現這個演演算法，我們需要：

將 4- 結點表示由三個 2- 結點組成的一棵平衡的子樹，根結點和兩個子結點都用紅連結相連；
在向下的過程中分解所有 4- 結點並進行顏色轉換；
和插入操作一樣，在向上的過程用旋轉將 4- 結點配平。
只需移動上面演演算法的 Put 方法中的一行程式碼就能實現 2-3-4 樹中的插入操作：將 ColorFlip 語句及其 if 語句一道遞迴呼叫之前（null 測試和比較操作之間）。

2.刪除最小鍵

從樹底部的 3- 結點刪除鍵很簡單，但從 2- 結點刪除一個鍵會留下一個空連結，這樣會破環樹的完美平衡性。
為了保證我們不會刪除一個 2- 結點，我們沿著左連線向下進行變換，確保當前結點不是 2- 結點（可能是 3- 結點，也可能是臨時 4- 結點）。
首先，根結點可能有兩種情況。如果根結點是 2- 結點且它的兩個子結點都是 2- 結點，我們可以直接將這三個結點變成一個 4- 結點；否則我們需要保證根結點的左子結點不是 2- 結點，如有必要可以從它右側的兄弟結點“借”一個鍵來。如圖。在沿著左連線向下的過程中，保證一下情況之一成立：
如果當前結點的左子結點不是 2- 結點，完成；
如果當前結點的左子結點是 2- 結點而它的親兄弟結點不是 2- 結點，將左子結點的兄弟結點中的一個鍵移動到左子結點中；
如果當前結點的左子結點和它的親兄弟結點都是 2- 結點，將左子結點，父結點中的最小鍵和左子節點最近的兄弟結點合併成一個 4- 結點，使父結點由 3- 結點變成 2- 結點或者由 4- 結點變成 3- 結點。
在遍歷的過程中執行這個過程，最後能夠得到一個含有最小鍵的 3- 結點或者 4- 結點，然後就可以直接從中將其刪除。我們再回頭向上分解所有臨時的 4- 結點。

3.刪除操作

在查詢路徑上進行和刪除最小鍵相同的變換同樣可以保證在查詢過程中任意當前結點均不是 2- 結點。如果被查詢的鍵在樹的底部，可以直接刪除。如果不在，需要將它和它的後繼結點交換，和二叉查詢樹
一樣。

紅黑樹的性質

研究紅黑樹的性質就是要檢查對應的 2-3 樹並對相應的 2-3 樹進行分析過程。所有基於紅黑樹的符號表實現都能保證操作的執行時間為對數級別（範圍查詢除外）。
無論鍵的插入順序如何，紅黑樹都幾乎是完美平衡的。一棵大小為 N 的紅黑樹的高度不會超過 2lgN 。紅黑樹的最壞情況是它所對應的 2-3 樹中構成最左邊的路徑結點全部都是 3- 結點而其餘均是 2- 結點。
最左邊的路徑長度是隻包含 2- 結點的路徑長度（~lgN）的兩倍。使用隨機的鍵序列，在一棵大小為 N 的紅黑樹中一次查詢所需的比較次數約為（1.00 lgN - 0.5）,根結點到任意結點的平均路徑長度 ~ 1.00lgN 。
紅黑樹的 Get 方法不會檢查結點的顏色，因此平衡性相關的操作不會產生任何負擔；因為樹是平衡的，所以查詢比二叉查詢樹更快。每個只會被插入一次，但卻可能查詢無數次。