JavaScript數據結構——樹的實現

来源:https://www.cnblogs.com/jaxu/archive/2019/08/09/11309385.html
-Advertisement-
Play Games

在電腦科學中，樹是一種十分重要的數據結構。樹被描述為一種分層數據抽象模型，常用來描述數據間的層級關係和組織結構。樹也是一種非順序的數據結構。下圖展示了樹的定義： 在介紹如何用JavaScript實現樹之前，我們先介紹一些和樹相關的術語。 如上圖所示，一棵完整的樹包含一個位於樹頂部的節點，稱之為根節 ...


　　在電腦科學中，樹是一種十分重要的數據結構。樹被描述為一種分層數據抽象模型，常用來描述數據間的層級關係和組織結構。樹也是一種非順序的數據結構。下圖展示了樹的定義：

　　在介紹如何用JavaScript實現樹之前，我們先介紹一些和樹相關的術語。

　　如上圖所示，一棵完整的樹包含一個位於樹頂部的節點，稱之為根節點（11），它沒有父節點。樹中的每一個元素都叫做一個節點，節點分為內部節點（圖中顯示為黃色的節點）和外部節點（圖中顯示為灰色的節點），至少有一個子節點的節點稱為內部節點，沒有子元素的節點稱為外部節點或葉子節點。一個節點可以有祖先（根節點除外）和後代。子樹由節點本身和它的後代組成，如上圖中三角虛框中的部分就是一棵子樹。節點擁有的子樹的個數稱之為節點的度，如上圖中除葉子節點的度為0外，其餘節點的度都為2。從根節點開始，根為第1層，第一級子節點為第2層，第二級子節點為第3層，以此類推。樹的高度（深度）由樹中節點的最大層級決定（上圖中樹的高度為4）。

　　在一棵樹中，具有相同父節點的一組節點稱為兄弟節點，如上圖中的3和6、5和9等都是兄弟節點。

二叉樹

　　二叉樹中的節點最多只能有兩個子節點，一個是左子節點，一個是右子節點。左右子節點的順序不能顛倒。因此，二叉樹中不存在度大於2的節點。

　　二叉搜索樹（BST——Binary Search Tree）是二叉樹的一種，它規定在左子節點上存儲小（比父節點）的值，在右子節點上（比父節點）存儲大（或等於）的值。上圖就是一個二叉搜索樹。

　　下麵我們重點來看一下二叉搜索樹的實現。

　　根據二叉樹的描述，一個節點最多只有兩個子節點，我們可以使用《JavaScript數據結構——鏈表的實現與應用》一文中的雙向鏈表來實現二叉搜索樹中的每一個節點。下麵是二叉搜索樹的數據結構示意圖：

　　以下是我們要實現的BinarySearchTree類的骨架部分：

class BinarySearchTree {
    constructor () {
        this.root = null;
    }

    // 向樹中插入一個節點
    insert (key) {}

    // 在樹中查找一個節點
    search (key) {}

    // 通過中序遍歷方式遍歷樹中的所有節點
    inOrderTraverse () {}

    // 通過先序遍歷方式遍歷樹中的所有節點
    preOrderTraverse () {}

    // 通過後序遍歷方式遍歷樹中的所有節點
    postOrderTraverse () {}

    // 返回樹中的最小節點
    min () {}

    // 返回樹中的最大節點
    max () {}

    // 從樹中移除一個節點
    remove (key) {}
}

 　　先來看看向樹中添加一個節點。我們借用《JavaScript數據結構——鏈表的實現與應用》一文中的雙向鏈表DoubleLinkedList類來模擬樹中的節點，在DoubleLinkedList類中，每一個節點有三個屬性：element、next和prev。我們在這裡用element表示樹中節點的key，用next表示樹中節點的右子節點（right），用prev表示樹中節點的左子節點（left）。

insert (key) {
    let newNode = new Node(key);

    if (this.root === null) this.root = newNode;
    else insertNode(this.root, newNode);
}

　　當樹的root為null時，表示樹為空，這時直接將新添加的節點作為樹的根節點。否則，我們需要藉助於私有函數insertNode()來完成節點的添加。在insertNode()函數中，我們需要根據新添加節點的key的大小來遞歸查找樹的左側子節點或者右側子節點，因為根據我們的二叉搜索樹的定義，值小的節點永遠保存在左側子節點上，值大的節點（包括值相等的情況）永遠保存在右側子節點上。下麵是insertNode()函數的實現代碼：

let insertNode = function (node, newNode) {
    if (newNode.element < node.element) {
        if (node.prev === null) node.prev = newNode;
        else insertNode(node.prev, newNode);
    }
    else {
        if (node.next === null) node.next = newNode;
        else insertNode(node.next, newNode);
    }
};

　　所有新節點只能作為葉子節點被添加到樹中。在本文一開始給出的樹的結構圖中，如果要添加節點2，對應的操作步驟如下：

　　我們傳入樹的根節點，依次進行遞歸，找到對應的葉子節點，然後修改節點的prev（左子節點）或next（右子節點）指針，使其指向新添加的節點。在上例中，如果要添加節點4，它對應的位置應該是節點3的右子節點，因為4比3大。如果要添加節點21，對應的位置應該是節點25的左子節點......

　　下麵我們來看看樹的三種遍歷方式：

  • 前序遍歷（NLR——Preorder Traversal）也叫先序遍歷，訪問根節點的操作發生在遍歷其左右子樹之前。
  • 中序遍歷（LNR——Inorder Traversal），訪問根節點的操作發生在遍歷其左右子樹之間。
  • 後序遍歷（LRN——Postorder Traversal），訪問根節點的操作發生在遍歷其左右子樹之後。

　　下麵的三個方法對應樹的三種遍歷方式：

// 前序遍歷
let preOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        callback(node.element);
        preOrderTraverseNode(node.prev, callback);
        preOrderTraverseNode(node.next, callback);
    }
};

// 中序遍歷
let inOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        inOrderTraverseNode(node.prev, callback);
        callback(node.element);
        inOrderTraverseNode(node.next, callback);
    }
};

// 後續遍歷
let postOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        postOrderTraverseNode(node.prev, callback);
        postOrderTraverseNode(node.next, callback);
        callback(node.element);
    }
};

　　可以看到，這三個函數的內容很相似，只是調整了左右子樹和根節點的遍歷順序。這裡的callback是一個回調函數，可以傳入任何你想執行的函數，這裡我們傳入的函數內容是列印樹的節點的key值。我們將BinarySearchTree類的這三個遍歷方法的內容補充完整：

preOrderTraverse (callback) {
    preOrderTraverseNode(this.root, callback);
}

inOrderTraverse (callback) {
    inOrderTraverseNode(this.root, callback);
}

postOrderTraverse (callback) {
    postOrderTraverseNode(this.root, callback);
}

　　為了構建本文一開始的那棵樹，我們執行下麵的代碼，然後測試preOrderTraverse()方法：

let tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(9);
tree.insert(13);
tree.insert(20);
tree.insert(3);
tree.insert(6);
tree.insert(8);
tree.insert(10);
tree.insert(12);
tree.insert(14);
tree.insert(18);
tree.insert(25);

tree.preOrderTraverse((value) => console.log(value));

　　註意節點插入的順序，順序不同，你可能會得到不一樣的樹。preOrderTraverse()方法採用ES6的語法傳入了一個匿名函數作為參數callback的值，這個匿名函數的主要作用就是列印樹中節點的key值，可以對照上面三個遍歷樹節點的函數中的callback(node.element)語句，這裡的callback就是這個匿名函數，node.element就是節點的key值（還記得前面我們說過，借用雙向鏈表類DoubleLinkedList來模擬樹的節點嗎？）下麵是前序遍歷的執行結果：

11
7
5
3
6
9
8
10
15
13
12
14
20
18
25

　　我們參照前序遍歷的定義，借住下麵的示意圖來理解整個遍歷過程：

　　在前序遍歷函數preOrderTraverseNode()中，先執行callback(node.element)，然後再依次遞歸左子樹和右子樹。我們將樹的根節點作為第一個節點傳入，首先列印的就是根節點11，然後開始遍歷左子樹，這將依次列印左子樹中的所有左子節點，依次是7、5、3。當節點3的prev為null時，遞歸返回，繼續查找節點3的右子節點，此時節點3的next值也為null，於是繼續向上返回到節點5，開始遍歷節點5的右子節點，於是列印節點6......最終所有的節點就按照這個遞歸順序進行遍歷。

　　然後我們再來看看中序遍歷的情況。

tree.inOrderTraverse((value) => console.log(value));
3
5
6
7
8
9
10
11
12
13
14
15
18
20
25

 

　　在中序遍歷函數inOrderTraverseNode()中，先遞歸左子樹，然後執行callback(node.element)，最後再遞歸右子樹。同樣的，我們將根節點作為第一個節點傳入，遞歸到左子樹的最後一個左子節點3，由於節點3的prev為null，所以遞歸返回，列印節點3，然後繼續查找節點3的右子節點，節點3的next值也為null，遞歸返回到上一層節點5，開始列印節點5，之後再查找節點5的右子節點......最終整棵樹按照這個順序完成遍歷。

　　最後再來看看後序遍歷的情況。

tree.postOrderTraverse((value) => console.log(value));
3
6
5
8
10
9
7
12
14
13
18
25
20
15
11

 

　　在後序遍歷函數postOrderTraverseNode()中，先遞歸左子樹，然後再遞歸右子樹，最後執行callback(node.element)。同樣的，我們將根節點作為第一個節點傳入，遞歸到左子樹的最後一個左子節點3，由於節點3的prev為null，所以遞歸返回，此時繼續查找節點3的右子節點，節點3的next值也為null，遞歸返回並列印節點3，之後遞歸返回到上一層節點5，開始查找節點5的右子節點，節點5的右子節點是節點6，由於節點6是葉子節點，所以直接列印節點6，然後遞歸返回並列印節點5。之後遞歸再向上返回到節點7並遞歸節點7的右子節點......按照這個順序最終完成對整棵樹的遍歷。

　　接下來我們再來看看對樹的搜索。有三種要經常執行的搜索方式：

  • 搜索樹中的最小值
  • 搜索樹中的最大值
  • 搜索樹中的特定值

　　搜索樹中的最小值和最大值比較簡單，由於我們的二叉搜索樹規定了值小的節點永遠在左子樹（左子節點）中，值大（或相等）的節點永遠在右子樹（右子節點）中，所以，搜索最大值我們只需要遞歸查找樹的右子樹直到葉子節點，就能找到值最大的節點。搜索最小值只需要遞歸查找樹的左子樹直到葉子節點，就能找到值最小的節點。下麵是這兩個函數的實現：

let minNode = function (node) {
    if (node === null) return null;

    while (node && node.prev !== null) {
        node = node.prev;
    }
    return node;
};

let maxNode = function (node) {
    if (node === null) return null;

    while (node && node.next !== null) {
        node = node.next;
    }
    return node;
};

　　第三種方式是搜索特定的值，我們需要比較要搜索的值與當前節點的值，如果要搜索的值小於當前節點的值，則從當前節點開始遞歸查找左子數（左子節點）。如果要搜索的值大於當前節點的值，則從當前節點開始遞歸查找右子樹（右子節點）。按照這個邏輯，我們的searchNode()函數實現如下：

let searchNode = function (node, key) {
    if (node === null) return null;

    if (key < node.element) return searchNode(node.prev, key);
    else if (key > node.element) return searchNode(node.next, key);
    else return node;
};

　　如果找到了對應的節點，就返回該節點，否則就返回null。我們將BinarySearchTree類的這三個搜索方法的內容補充完整：

search (key) {
    return searchNode(this.root, key);
}

min () {
    return minNode(this.root);
}

max () {
    return maxNode(this.root);
}

　　下麵是一些測試用例及結果：

console.log(tree.min().element); // 3
console.log(tree.max().element); // 25
console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.'); // Key 1 not found.
console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.'); // Key 8 found.

　　讓我們來看一下search()方法的執行過程是怎樣的。

　　搜索key=1的節點，首先我們傳入樹的根節點和key=1，由於1小於根節點的值11，遞歸查找根節點的左子節點7，1<7，繼續查找節點7的左子節點，直到找到葉子節點3，1仍然小於3，但是節點3沒有左子節點了，所以返回false，整個遞歸開始向上返回，最終返回的結果是false，表示樹中沒有key=1的節點。

　　相應地，對於搜索key=8的節點，也是先遍歷根節點的左子節點7，由於8>7，所以會遍歷節點7的右子節點，找到節點9，8<9，遍歷節點9的左子節點，此時找到節點9的左子節點正好是8，所以返回true，然後整個遞歸向上返回，最終的返回結果就是true，表示樹中找到了key=8的節點。

　　最後我們再來看一下從樹中移除一個節點的過程，這個過程要稍微複雜一些。先來看看刪除樹節點的函數removeNode()的代碼，稍後我們再來詳細講解整個執行過程。

let removeNode = function (node, key) {
    if (node === null) return null;

    if (key < node.element) {
        node.prev = removeNode(node.prev, key);
        return node;
    }
    else if (key > node.element) {
        node.next = removeNode(node.next, key);
        return node;
    }
    else {
        // 第一種情況：一個葉子節點（沒有子節點）
        if (node.prev === null && node.next === null) {
            node = null;
            return node;
        }
        // 第二種情況：只包含一個子節點
        if (node.prev === null) {
            node = node.next;
            return node;
        }
        else if (node.next === null) {
            node = node.prev;
            return node;
        }

        // 第三種情況：有兩個子節點
        let aux = minNode(node.next);
        node.element = aux.element;
        node.next = removeNode(node.next, aux.element);
        return node;
    }
};

　　首先要找到樹中待刪除的節點，這需要進行遞歸遍歷，從根節點開始，如果key值小於當前節點的值，則遍歷左子樹，如果key值大於當前節點的值，則遍歷右子樹。註意，在遞歸遍歷的過程中，我們將node（這裡的node傳入的是樹的根節點）的prev指針或next指針逐級指向下一級節點，然後返回整個node。當找到要刪除的節點後，我們要處理三種情況：

  • 該節點為葉子節點（沒有子節點）
  • 該節點只有一個子節點（左子節點或右子節點）
  • 該節點有兩個子節點（左右子節點都存在）

 　　我們先看第一種情況：

　　假設我們要刪除節點6，傳入根節點11，整個執行過程如下：

  1. node=11，key=6，6<11，遞歸執行removeNode(7, 6)
  2. node=7，key=6，6<7，遞歸執行removeNode(5, 6)
  3. node=5，key=6，6>5，遞歸執行removeNode(6, 6)
  4. node=6，key=6，6=6，並且節點6的prev和next都為null，所以我們將節點6設置為null，並且返回null
  5. 遞歸返回到步驟3，節點5的next將獲取步驟4的返回值null
  6. 遞歸返回到步驟2，節點7的prev依然指向節點5，保持不變
  7. 遞歸返回到步驟1，節點11的prev依然指向節點7，保持不變
  8. 最後返回節點11

　　然後我們來看只有一個子節點的情況：

　　前面已經刪除了節點6，假設我們現在要刪除節點5，它有一個左子節點3，我們依然傳入根節點11，來看看整個執行過程：

  1. node=11，key=5，5<11，遞歸執行removeNode(7, 5)
  2. node=7，key=5，5<7，遞歸執行removeNode(5, 5)
  3. node=5，key=5，5=5，並且節點5的prev=3，next=null，所以我們將節點5替換成它的左子節點3，並返回節點3
  4. 遞歸返回到步驟2，節點7的next將獲取步驟3的返回值3
  5. 遞歸返回到步驟1，節點11的prev依然指向節點7，保持不變
  6. 最後返回節點11

　　我們不需要將節點5從記憶體中刪除，它會自動被JavaScript的垃圾回收器清理掉，這個在《JavaScript數據結構——鏈表的實現與應用》一文中已經介紹過。以上步驟是針對目標節點有左子節點的情況，對於有右子節點情況，執行過程是類似的。

　　最後再來看第三種情況：

　　前面已經刪除了節點6和節點5，現在我們要刪除節點15，它有左右子樹，我們傳入根節點11，來看下具體執行過程：

  1. node=11，key=15，15>11，遞歸執行removeNode(15, 15)
  2. node=15，key=15，15=15，此時我們需要找到節點15的右子樹中的最小節點18，將節點15的key替換成節點18的key，然後將節點15的next節點（即節點20）作為起始節點進行遍歷，找到並刪除節點18，最後再將節點15（此時它的key是18）的next指針指向節點20，並返回節點15
  3. 遞歸返回到步驟1，節點11的next依然指向節點15，但此時節點15的key已經變成18了
  4. 最後返回節點11

　　試想一下，當刪除節點15之後，為了保證我們的二叉搜索樹結構穩定，必須用節點15的右子樹中的最小節點來替換節點15，如果直接將11的next指向20，則20將會有三個子節點13、18、25，這顯然已經不符合我們二叉樹的定義了。如果將節點25用來替換節點15，節點20的值比節點25的值小，不應該出現在右子節點，這也不符合我們的二叉搜索樹的定義。所以，只有按照上述過程才能既保證不破壞樹的結構，又能刪除節點。

　　我們已經完成了一開始我們定義的二叉搜索樹BinarySearchTree類的所有方法，下麵是它的完整代碼：

  1 let insertNode = function (node, newNode) {
  2     if (newNode.element < node.element) {
  3         if (node.prev === null) node.prev = newNode;
  4         else insertNode(node.prev, newNode);
  5     }
  6     else {
  7         if (node.next === null) node.next = newNode;
  8         else insertNode(node.next, newNode);
  9     }
 10 };
 11 
 12 let preOrderTraverseNode = function (node, callback) {
 13     if (node !== null) {
 14         callback(node.element);
 15         preOrderTraverseNode(node.prev, callback);
 16         preOrderTraverseNode(node.next, callback);
 17     }
 18 };
 19 
 20 let inOrderTraverseNode = function (node, callback) {
 21     if (node !== null) {
 22         inOrderTraverseNode(node.prev, callback);
 23         callback(node.element);
 24         inOrderTraverseNode(node.next, callback);
 25     }
 26 };
 27 
 28 let postOrderTraverseNode = function (node, callback) {
 29     if (node !== null) {
 30         postOrderTraverseNode(node.prev, callback);
 31         postOrderTraverseNode(node.next, callback);
 32         callback(node.element);
 33     }
 34 };
 35 
 36 let minNode = function (node) {
 37     if (node === null) return null;
 38 
 39     while (node && node.prev !== null) {
 40         node = node.prev;
 41     }
 42     return node;
 43 };
 44 
 45 let maxNode = function (node) {
 46     if (node === null) return null;
 47 
 48     while (node && node.next !== null) {
 49         node = node.next;
 50     }
 51     return node;
 52 };
 53 
 54 let searchNode = function (node, key) {
 55     if (node === null) return false;
 56 
 57     if (key < node.element) return searchNode(node.prev, key);
 58     else if (key > node.element) return searchNode(node.next, key);
 59     else return true;
 60 };
 61 
 62 let removeNode = function (node, key) {
 63     if (node === null) return null;
 64 
 65     if (key < node.element) {
 66         node.prev = removeNode(node.prev, key);
 67         return node;
 68     }
 69     else if (key > node.element) {
 70         node.next = removeNode(node.next, key);
 71         return node;
 72     }
 73     else {
 74         // 第一種情況：一個葉子節點（沒有子節點）
 75         if (node.prev === null && node.next === null) {
 76             node = null;
 77             return node;
 78         }
 79         // 第二種情況：只包含一個子節點
 80         if (node.prev === null) {
 81             node = node.next;
 82             return node;
 83         }
 84         else if (node.next === null) {
 85             node = node.prev;
 86             return node;
 87         }
 88 
 89         // 第三種情況：有兩個子節點
 90         let aux = minNode(node.next);
 91         node.element = aux.element;
 92         node.next = removeNode(node.next, aux.element);
 93         return node;
 94     }
 95 };
 96 
 97 class BinarySearchTree {
 98     constructor () {
 99         this.root = null;
100     }
101 
102     // 向樹中插入一個節點
103     insert (key) {
104         let newNode = new Node(key);
105 
106         if (this.root === null) this.root = newNode;
107         else insertNode(this.root, newNode);
108     }
109 
110     // 在樹中查找一個節點
111     search (key) {
112         return searchNode(this.root, key);
113     }
114 
115     // 通過先序遍歷方式遍歷樹中的所有節點
116     preOrderTraverse (callback) {
117         preOrderTraverseNode(this.root, callback);
118     }
119 
120     // 通過中序遍歷方式遍歷樹中的所有節點
121     inOrderTraverse (callback) {
122         inOrderTraverseNode(this.root, callback);
123     }
124 
125     // 通過後序遍歷方式遍歷樹中的所有節點
126     postOrderTraverse (callback) {
127         postOrderTraverseNode(this.root, callback);
128     }
129 
130     // 返回樹中的最小節點
131     min () {
132         return minNode(this.root);
133     }
134 
135     // 返回樹中的最大節點
136     max () {
137         return maxNode(this.root);
138     }
139 
140     // 從樹中移除一個節點
141     remove (key) {
142         this.root = removeNode(this.root, key);
143     }
144 }
BinarySearchTree

自平衡樹

　　上面的BST樹（二叉搜索樹）存在一個問題，樹的一條邊可能會非常深，而其它邊卻只有幾層，這會在這條很深的分支上添加、移除和搜索節點時引起一些性能問題。如下圖所示：

　　為瞭解決這個問題，我們引入了自平衡二叉搜索樹（AVL——Adelson-Velskii-Landi）。在AVL中，任何一個節點左右兩棵子樹的高度之差最多為1，添加或移除節點時，AVL樹會嘗試自平衡。對AVL樹的操作和對BST樹的操作一樣，不同點在於我們還需要重新平衡AVL樹，在講解對AVL樹的平衡操作之前，我們先看一下什麼是AVL樹的平衡因數。

　　前面我們介紹過什麼是樹（子樹）的高度，對於AVL樹來說，每一個節點都保存一個平衡因數。

　　節點的平衡因數 = 左子樹的高度 - 右子樹的高度

　　觀察下麵這棵樹，我們在上面標註了每個節點的平衡因數的值：

　　所有子節點的平衡因數都為0，因為子節點沒有子樹。節點5的左右子樹的高度都為1，所以節點5的平衡因數是0。節點9的左子樹高度為1，右子樹高度為0，所以節點9的平衡因數是+1。節點13的左子樹高度為0，右子樹高度為1，所以節點13的平衡因數是-1......AVL樹的所有節點的平衡因數保持三個值：0、+1或-1。同時，我們也註意到，當某個節點的平衡因數為+1時，它的子樹是向左傾斜的（left-heavy）；而當某個節點的平衡因數為-1時，它的子樹是向右傾斜的（right-heavy）；當節點的平衡因數為0時，該節點是平衡的。一顆子樹的根節點的平衡因數代表了該子樹的平衡性。

　　為了使AVL樹重新達到平衡狀態，我們需要對AVL樹中的部分節點進行重新排列，使其既符合二叉搜索樹的定義，又符合自平衡二叉樹的定義，這個過程叫做AVL樹的旋轉。

　　AVL樹的旋轉一共分為四種：

  • LL（left-left）旋轉，新添加的節點位於樹的根節點的左子樹的左子樹上。以非平衡因數的節點為中心將整棵樹向右旋轉。
  • LR（left-right）旋轉，新添加的節點位於樹的根節點的左子樹的右子樹上。先執行RR旋轉，然後再執行LL旋轉。
  • RR（right-right）旋轉，新添加的節點位於樹的根節點的右子樹的右子樹上。以非平衡因數的節點為中心將整棵樹向左旋轉。
  • RL（right-left）旋轉，新添加的節點位於樹的根節點的右子樹的左子樹上。先執行LL旋轉，然後再執行RR旋轉。

　　下麵是這四種旋轉的操作示意圖，後面我們會詳細介紹每一種旋轉的操作過程：

　　對於LL旋轉，在節點5的右子節點上添加節點4與在左子節點上添加節點3等同。對於LR旋轉，在節點9的左子節點上添加節點8與在右子節點上添加節點10等同。對於RR旋轉，在節點20的右子節點上添加節點25與在左子節點上添加節點18等同。對於RL旋轉，在節點13的右子節點上添加節點14與在左子節點上添加節點12等同。

　　我們的自平衡二叉樹AVLTree類將從BinarySearchTree類繼承，同時我們需要新增一個方法getNodeHeight()用來獲取任意節點的高度。

class AVLTree extends BinarySearchTree {
    constructor () {
        super();
    }

    // 計算節點的高度
    getNodeHeight (node) {
        if (node === null) return 0;
        return Math.max(this.getNodeHeight(node.prev), this.getNodeHeight(node.next)) + 1;
    };
}

　　測試一下getNodeHeight()方法，我們還是以本文一開始的那棵樹為例，然後看一下不同節點的高度。

let tree = new AVLTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(9);
tree.insert(13);
tree.insert(20);
tree.insert(3);
tree.insert(6);
tree.insert(8);
tree.insert(10);
tree.insert(12);
tree.insert(14);
tree.insert(18);
tree.insert(25);

console.log(tree.getNodeHeight(tree.root)); // 4
console.log(tree.getNodeHeight(tree.search(7))); // 3
console.log(tree.getNodeHeight(tree.search(5))); // 2
console.log(tree.getNodeHeight(tree.min(7))); // 1

　　根節點的高度為4，最小節點3的高度為1，節點5和節點7的高度分別為2和3。

　　下麵是四種旋轉對應的實現代碼：

/**
 * LL旋轉: 向右旋轉
 *
 *       b                           a
 *      / \                         / \
 *     a   e -> rotationLL(b) ->   c   b
 *    / \                         /   / \
 *   c   d                       f   d   e
 *  /
 * f
 *
 * @param node Node<T>
 */
rotationLL(node) {
    let tmp = node.prev;
    node.prev = tmp.next;
    tmp.next = node;
    return tmp;
}

/**
 * RR旋轉: 向左旋轉
 *
 *     a                              b
 *    / \                            / \
 *   c   b   -> rotationRR(a) ->    a   e
 *      / \                        / \   \
 *     d   e                      c   d   f
 *          \
 *           f
 *
 * @param node Node<T>
 */
rotationRR(node) {
    let tmp = node.next;
    node.next = tmp.prev;
    tmp.prev = node;
    return tmp;
}

/**
 * LR旋轉: 先向左旋轉，然後再向右旋轉
 * @param node Node<T>
 */
rotationLR(node) {
    node.prev = this.rotationRR(node.prev);
    return this.rotationLL(node);
}

/**
 * RL旋轉: 先向右旋轉，然後再向左旋轉
 * @param node Node<T>
 */
rotationRL(node) {
    node.next = this.rotationLL(node.next);
    return this.rotationRR(node);
}

　　對於LL旋轉和RR旋轉，我們可以按照上面的示意圖來看下執行過程。

　　LL旋轉，node=11，node.prev是7，所以tmp=7。然後將node.prev指向tmp.next，即將11的prev指向9。接著將tmp.next指向node，即將7的next指向11。即完成了圖中所示的旋轉。

　　RR旋轉，node=11，node.next是15，所以tmp=15。然後將node.next指向tmp.prev，即將11的next指向13。接著將tmp.prev指向node，即將15的prev指向11。即完成了圖中所示的旋轉。

　　LR旋轉是RR旋轉和LL旋轉的組合：

　　RL旋轉是LL旋轉和RR旋轉的組合：

　　按照上面給出的示意圖，我們的AVLTree類的insert()方法的實現如下：

insert (key) {
    super.insert(key);

    // 左子樹高度大於右子樹高度
    if (this.getNodeHeight(this.root.prev) - this.getNodeHeight(this.root.next) > 1) {
        if (key < this.root.prev.element) {
            this.root = this.rotationLL(this.root);
        }
        else {
            this.root = this.rotationLR(this.root);
        }
    }
    // 右子樹高度大於左子樹高度
    else if (this.getNodeHeight(this.root.next) - this.getNodeHeight(this.root.prev) > 1) {
        if (key > this.root.next.element) {
            this.root = this.rotationRR(this.root);
        }
        else {
            this.root = this.rotationRL(this.root);
        }
    }
}

　　我們依次測試一下這四種情況。按照上面示意圖中樹的結構添加節點，然後按照前序遍歷的方式列印節點的key。

　　LL旋轉的結果：

let tree = new AVLTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(9);
tree.insert(3);

tree.preOrderTraverse((value) => console.log(value));
7
5
3
11
9
15

　　LR旋轉的結果：

let tree = new AVLTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(9);
tree.insert(8);

tree.preOrderTraverse((value) => console.log(value));
9
7
5
8
11
15

　　RR旋轉的結果：

let tree = new AVLTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(13);
tree.insert(20);
tree.insert(25);

tree.preOrderTraverse((value) => console.log(value));
15
11
7
13
20
25

　　RL旋轉的結果：

let tree = new
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Redis 初步接觸
    Redis簡介 Redis是什麼 Redis是一個開源的，使用ANSI C 編寫，高性能的Key Value的NoSQL資料庫。 Redis特點 1. 基於記憶體 2. 可持久化數據 3. 具有豐富的數據結構類型，適應非關係型數據的存儲需求 4. 支持絕大多數主流開發語言，如C、C++、Java、Py ...
  • 什麼是實時流式計算？
    實時流式計算，也就是RealTime,Streaming,Analyse,在不同的領域有不同的定義,這裡我們說的是大數據領域的實時流式計算。 實時流式計算,或者是實時計算,流式計算,在大數據領域都是差不多的概念。那麼，到底什麼是實時流式計算呢？ 谷歌大神Tyler Akidau在《the world ...
  • Gradle-構建生命周期
    每一個 Gradle 構建都會按照相同的順序經歷三個不同的階段:初始化、配置、執行。 ...
  • iOS面試題總結
    1. 多線程的底層實現？ 2. 線程間怎麼通信？ 3. 網路圖片處理問題中怎麼解決一個相同的網路地址重覆請求的問題？ 4. 用NSOpertion和NSOpertionQueue處理A，B，C三個線程，要求執行完A，B後才能執行C，怎麼做？ 5. 列舉cocoa中常見對幾種多線程的實現，並談談多線程 ...
  • Android 8.1 自定義熱點的時候設置了熱點maxLength="32"，但是在希伯來語等狀態下還是發現在沒到32個字元之前就無法把熱點設置成功了
    初步認為應該是與熱點名稱的位元組數有關。 然後開始查看源碼。 /Settings/res/xml/tether_prefs.xml 中的 發現了熱點設置界面在HotspotSettings 裡面， 在HotspotSettings中點擊設置wifi熱點，進入/Settings/src/com/andr ...
  • react-native 鍵盤遮擋輸入框
    Android上已經自動對鍵盤遮擋輸入框做了處理，所以我們只需要關註ios。 1.首先引入 KeyboardAvoidingView 2.然後在頁面的最外層加上 KeyboardAvoidingView 如果適配ios和Android，可以將頁面提取出來 ...
  • Android定時鎖屏功能實現（AlarmManager定時部分）
    菜鳥入坑記——第一篇 關鍵字：AlarmManager 一、AlarmManager簡介： 參考網址：https://www.jianshu.com/p/8a2ce9d02640 參考網站：https://www.runoob.com/w3cnote/android-tutorial-alarmma ...
  • CSS 樣式的使用方式、選擇器
    在html中使用css的三種方式： 1、行內樣式：同過元素的style屬性來設置 屬性之間分號隔開。 2、內部樣式：在<head>的<style>元素中定義css樣式 3、外部樣式：在css文件中定義css樣式，然後在html的<head>中通過<style>引入外部樣式表 css文件中不加<sty ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類