樹
樹是一種分層數(shù)據(jù)的抽象模型。現(xiàn)實(shí)生活中最常見的樹的例子是家譜肚逸，或是公司的組織架構(gòu)圖
- 樹的相關(guān)術(shù)語
一個樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。每個節(jié)點(diǎn)都有一個父節(jié)點(diǎn)（除了頂部的第一個節(jié)點(diǎn)）以及零個或多個子節(jié)點(diǎn)
樹
根據(jù)上圖:
- 位于樹頂部的節(jié)點(diǎn)叫做
根節(jié)點(diǎn)(11) - 樹中的每個元素都叫作節(jié)點(diǎn)彬坏，節(jié)點(diǎn)分為
內(nèi)部節(jié)點(diǎn)和外部節(jié)點(diǎn)- 至少有一個子節(jié)點(diǎn)的節(jié)點(diǎn)稱為內(nèi)部節(jié)點(diǎn)（7朦促、5、9栓始、15务冕、13 和 20 是內(nèi)部節(jié)點(diǎn)）
- 沒有子元素的節(jié)點(diǎn)稱為外部節(jié)點(diǎn)或葉節(jié)點(diǎn)（3、6幻赚、8禀忆、10、12落恼、14油湖、18 和 25 是葉節(jié)點(diǎn)）
- 一個節(jié)點(diǎn)可以有祖先和后代
- 一個節(jié)點(diǎn)（除了根節(jié)點(diǎn)）的祖先包括父節(jié)點(diǎn)、祖父節(jié)點(diǎn)领跛、曾祖父節(jié)點(diǎn)等, 節(jié)點(diǎn) 5 的祖先有節(jié)點(diǎn) 7 和節(jié)點(diǎn) 11乏德，
- 一個節(jié)點(diǎn)的后代包括子節(jié)點(diǎn)、孫子節(jié)點(diǎn)、曾孫節(jié)點(diǎn)等, 節(jié)點(diǎn) 5 后代有節(jié)點(diǎn) 3 和節(jié)點(diǎn) 6
- 樹的另一個術(shù)語是
子樹- 子樹由節(jié)點(diǎn)和它的后代構(gòu)成喊括。例如胧瓜，節(jié)點(diǎn) 13、12 和 14 構(gòu)成了上圖中樹的一棵子樹
- 節(jié)點(diǎn)的一個屬性是
深度- 節(jié)點(diǎn)的深度取決于它的祖先節(jié)點(diǎn)的數(shù)量郑什。比如府喳，節(jié)點(diǎn) 3 有 3 個祖先節(jié)點(diǎn)（5、7 和 11）蘑拯，它的深度為 3
- 樹的高度取決于所有
節(jié)點(diǎn)深度的最大值- 一棵樹也可以被分解成層級钝满。根節(jié)點(diǎn)在第 0 層，它的子節(jié)點(diǎn)在第 1 層申窘，以此類推弯蚜。上圖中的樹的高度為 3（最大高度已在圖中表示——第 3 層）
- 二叉樹和二叉搜索樹
二叉樹中的節(jié)點(diǎn)最多只能有兩個子節(jié)點(diǎn)：一個是左側(cè)子節(jié)點(diǎn)，另一個是右側(cè)子節(jié)點(diǎn), 二叉搜索樹（BST）是二叉樹的一種剃法，但是只允許你在左側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）小的值碎捺，在右側(cè)節(jié)點(diǎn)存儲（比父節(jié)點(diǎn)）大的值。上一節(jié)的圖中就展現(xiàn)了一棵二叉搜索樹
- 創(chuàng)建二叉搜索樹
(BinarySearchTree)類
二叉搜索樹數(shù)據(jù)結(jié)構(gòu)組織方式
上圖展現(xiàn)了二叉搜索樹數(shù)據(jù)結(jié)構(gòu)的組織方式, 先來創(chuàng)建 Node 類來表示二叉搜索樹中的每個節(jié)點(diǎn)
和鏈表一樣, 我們通過指針(引用)來表示節(jié)點(diǎn)之間的關(guān)系, 樹也是用兩個指針, 但一個指向
左側(cè)子節(jié)點(diǎn), 另一個指向右側(cè)子節(jié)點(diǎn), 不同于在之前的章節(jié)中將節(jié)點(diǎn)本身稱作節(jié)點(diǎn)或項贷洲，我們將會稱其為鍵
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
聲明一個 BinarySearchTree 類的基本結(jié)構(gòu)
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
// 將聲明一個變量以控制此數(shù)據(jù)結(jié)構(gòu)的第一個節(jié)點(diǎn)收厨。在樹中，它不再是 head优构，而是 root
this.root = null;
}
}
-
實(shí)現(xiàn)一些方法
-
insert(key):想樹中插入一個新的鍵 -
search(key):向樹中查找一個鍵, 如果節(jié)點(diǎn)存在, 返回 true, 否則返回 false -
inOrderTraverse():通過中序遍歷方式遍歷所有節(jié)點(diǎn) -
preOrderTraverse():通過先序遍歷方式遍歷所有節(jié)點(diǎn) -
postOrderTravsese():通過后序遍歷方式遍歷所有節(jié)點(diǎn) -
min():返回樹中的最小值/鍵 -
max():返回樹中的最大的值/鍵 -
remove(key):從樹中移除某個鍵
-
向二叉搜索樹插入一個值
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
// 將聲明一個變量以控制此數(shù)據(jù)結(jié)構(gòu)的第一個節(jié)點(diǎn)诵叁。在樹中，它不再是 head钦椭，而是 root
this.root = null;
}
//
// 如果樹非空黎休，需要找到插入新節(jié)點(diǎn)的位置。因此玉凯，在調(diào)用 insertNode 方法時要通過參數(shù)傳入樹的根節(jié)點(diǎn)和要插入的節(jié)點(diǎn)
insertNode(node, key) {
// 如果新節(jié)點(diǎn)的鍵小于當(dāng)前節(jié)點(diǎn)的鍵
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
// 檢查當(dāng)前節(jié)點(diǎn)的左側(cè)子節(jié)點(diǎn), 如果它沒有左側(cè)子節(jié)點(diǎn)
if (node.left == null) {
// 在那里插入新的節(jié)點(diǎn)
node.left = new Node(key);
// 有左側(cè)子節(jié)點(diǎn)势腮，需要通過遞歸調(diào)用 insertNode方法
} else {
this.insertNode(node.left, key);
}
} else {
// 節(jié)點(diǎn)的鍵比當(dāng)前節(jié)點(diǎn)的鍵大，同時當(dāng)前節(jié)點(diǎn)沒有右側(cè)子節(jié)點(diǎn)
if (node.right == null) {
node.right = new Node(key);
// 有右側(cè)子節(jié)點(diǎn)漫仆，同樣需要遞歸調(diào)用 insertNode 方法
} else {
this.insertNode(node.right, key);
}
}
}
insert(key) {
// 嘗試插入的樹節(jié)點(diǎn)是否為第一個節(jié)點(diǎn)
if (this.root == null) {
// 創(chuàng)建一個 Node 類的實(shí)例并將它賦值給 root 屬性來將 root 指向這個新節(jié)點(diǎn), 左指針和右指針的值會由構(gòu)造函數(shù)自動設(shè)置為 null
this.root = new Node(key);
} else {
this.insertNode(this.root, key);
}
}
}
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
insert
- 樹的遍歷之中序遍歷
遍歷一棵樹是指訪問樹的每個節(jié)點(diǎn)并對它們進(jìn)行某種操作的過程, 訪問樹的所有節(jié)點(diǎn)有三種方式：中序捎拯、先序和后序
中序遍歷
中序遍歷是一種以上行順序訪問 BST 所有節(jié)點(diǎn)的遍歷方式，也就是以從最小到最大的順序訪問所有節(jié)點(diǎn)
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
// 將聲明一個變量以控制此數(shù)據(jù)結(jié)構(gòu)的第一個節(jié)點(diǎn)盲厌。在樹中署照，它不再是 head，而是 root
this.root = null;
}
/**
* 中序遍歷
* @param {接收一個回調(diào)函數(shù)作為參數(shù)} callback
*/
inOrderTraverse(callback) {
// 定義我們對遍歷到的每個節(jié)點(diǎn)進(jìn)行的操作
this.inOrderTraverseNode(this.root, callback);
}
// 輔助方法吗浩，來接收一個節(jié)點(diǎn)和對應(yīng)的回調(diào)函數(shù)作為參數(shù)
inOrderTraverseNode(node, callback) {
// 首先要檢查以參數(shù)形式傳入的節(jié)點(diǎn)是否為 null, 停止遞歸繼續(xù)執(zhí)行的判斷條件
if (node != null) {
// 遞歸調(diào)用相同的函數(shù)來訪問左側(cè)子節(jié)點(diǎn), 再訪問右側(cè)子節(jié)點(diǎn)
this.inOrderTraverseNode(node.left, callback);
callback(node.key);
this.inOrderTraverseNode(node.right, callback);
}
}
}
const printNode = (value) => console.log(value); // {6}
tree.inOrderTraverse(printNode); // {7}
中序遍歷
- 樹的遍歷之先序遍歷
先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問每個節(jié)點(diǎn)的, 先序遍歷的一種應(yīng)用是打印一個結(jié)構(gòu)化的文檔
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
// 將聲明一個變量以控制此數(shù)據(jù)結(jié)構(gòu)的第一個節(jié)點(diǎn)建芙。在樹中，它不再是 head懂扼，而是 root
this.root = null;
}
preOrderTraveser(callback) {
this.preOrderTraveserNode(this.root, callback);
}
preOrderTraveserNode(node, callback) {
if (node != null) {
// 先序遍歷會先訪問節(jié)點(diǎn)本身
callback(node.key);
// 再訪問左側(cè)子節(jié)點(diǎn)
this.preOrderTraveserNode(node.left, callback);
// 在訪問右側(cè)子節(jié)點(diǎn)
this.preOrderTraveserNode(node.right, callback);
}
}
}
// 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
先序遍歷路徑
- 后序遍歷
后序遍歷則是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)禁荸，再訪問節(jié)點(diǎn)本身右蒲。后序遍歷的一種應(yīng)用是計算一個目錄及其子目錄中所有文件所占空間的大小
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
// 將聲明一個變量以控制此數(shù)據(jù)結(jié)構(gòu)的第一個節(jié)點(diǎn)。在樹中赶熟，它不再是 head瑰妄，而是 root
this.root = null;
}
// 后序遍歷
postOrderTraverse(callback) {
this.postOrderTraverseNode(this.root, callback);
}
postOrderTraverseNode(node, callback) {
if (node != null) {
// 后序遍歷會先訪問左側(cè)子節(jié)點(diǎn)
this.postOrderTraverseNode(node.left, callback);
// 然后是右側(cè)子節(jié)點(diǎn)
this.postOrderTraverseNode(node.right, callback);
// 最后是父節(jié)點(diǎn)本身
callback(node.key);
}
}
}
// 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
后序
搜索樹中的值
- 搜索最大值和最小值
看樹中最大值和最小值
// 上圖樹的最左端是最小值, 最右端是最大值
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
// 將聲明一個變量以控制此數(shù)據(jù)結(jié)構(gòu)的第一個節(jié)點(diǎn)。在樹中映砖，它不再是 head间坐，而是 root
this.root = null;
}
min() {
return this.minNode(this.root);
}
// 允許我們從樹中任意一個節(jié)點(diǎn)開始尋找最小的鍵, 找到最左端
minNode(node) {
let current = node;
while (current != null && current.left != null) {
current = current.left;
}
return current;
}
max() {
return this.maxNode(this.root);
}
// 沿著樹的右邊進(jìn)行遍歷
maxNode(node) {
let current = node;
while (current != null && current.right != null) {
current = current.right;
}
return current;
}
}
- 搜索一個特定的值
search 方法
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
// 將聲明一個變量以控制此數(shù)據(jù)結(jié)構(gòu)的第一個節(jié)點(diǎn)。在樹中邑退，它不再是 head竹宋，而是 root
this.root = null;
}
// 聲明 search 方法。和 BST 中聲明的其他方法的模式相同地技，我們將會使用一個輔助方法
search(key) {
return this.searchNode(this.root, key);
}
// searchNode 方法可以用來尋找一棵樹或其任意子樹中的一個特定的值
searchNode(node, key) {
// 驗證作為參數(shù)傳入的 node 是否合法
if (node == null) return false;
// 要找的鍵比當(dāng)前的節(jié)點(diǎn)小, 在左側(cè)的子樹上搜索
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
return this.searchNode(node.left, key);
// 要找的鍵比當(dāng)前的節(jié)點(diǎn)大, 從右側(cè)子節(jié)點(diǎn)開始繼續(xù)搜索
} else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
return this.searchNode(node.right, key);
} else {
return true;
}
}
}
// 執(zhí)行該方法來查找 1 這個鍵
/**
* 調(diào)用 searchNode 方法蜈七，傳入根節(jié)點(diǎn)作為參數(shù), node[root[11]]不為 null
* key[1] < node[11]為真, 再次調(diào)用 searchNode 方法，傳入 node[7], key[1]作為參數(shù)
* node[7]不為 null乓土，因此繼續(xù)執(zhí)行行
* key[1] < node[7]為真, 再次調(diào)用 searchNode 方法宪潮，傳入 node[5], key[1]作為參數(shù)
* node[5]不為 null溯警，因此繼續(xù)執(zhí)行行
* key[1] < node[5]為真, 入 node[3], key[1]作為參數(shù)
* /
- 移除一個節(jié)點(diǎn)
為 BST 實(shí)現(xiàn)的下一個趣苏、也是最后一個方法是 remove 方法
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor(compareFn = defaultCompare) {
this.compareFn = compareFn;
// 將聲明一個變量以控制此數(shù)據(jù)結(jié)構(gòu)的第一個節(jié)點(diǎn)。在樹中梯轻，它不再是 head食磕，而是 root
this.root = null;
}
//
// 如果樹非空，需要找到插入新節(jié)點(diǎn)的位置喳挑。因此彬伦，在調(diào)用 insertNode 方法時要通過參數(shù)傳入樹的根節(jié)點(diǎn)和要插入的節(jié)點(diǎn)
insertNode(node, key) {
// 如果新節(jié)點(diǎn)的鍵小于當(dāng)前節(jié)點(diǎn)的鍵
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
// 檢查當(dāng)前節(jié)點(diǎn)的左側(cè)子節(jié)點(diǎn), 如果它沒有左側(cè)子節(jié)點(diǎn)
if (node.left == null) {
// 在那里插入新的節(jié)點(diǎn)
node.left = new Node(key);
// 有左側(cè)子節(jié)點(diǎn)，需要通過遞歸調(diào)用 insertNode方法
} else {
this.insertNode(node.left, key);
}
} else {
// 節(jié)點(diǎn)的鍵比當(dāng)前節(jié)點(diǎn)的鍵大伊诵，同時當(dāng)前節(jié)點(diǎn)沒有右側(cè)子節(jié)點(diǎn)
if (node.right == null) {
node.right = new Node(key);
// 有右側(cè)子節(jié)點(diǎn)单绑，同樣需要遞歸調(diào)用 insertNode 方法
} else {
this.insertNode(node.right, key);
}
}
}
insert(key) {
// 嘗試插入的樹節(jié)點(diǎn)是否為第一個節(jié)點(diǎn)
if (this.root == null) {
// 創(chuàng)建一個 Node 類的實(shí)例并將它賦值給 root 屬性來將 root 指向這個新節(jié)點(diǎn), 左指針和右指針的值會由構(gòu)造函數(shù)自動設(shè)置為 null
this.root = new Node(key);
} else {
this.insertNode(this.root, key);
}
}
/**
* 中序遍歷
* @param {接收一個回調(diào)函數(shù)作為參數(shù)} callback
*/
inOrderTraverse(callback) {
// 定義我們對遍歷到的每個節(jié)點(diǎn)進(jìn)行的操作
this.inOrderTraverseNode(this.root, callback);
}
// 輔助方法，來接收一個節(jié)點(diǎn)和對應(yīng)的回調(diào)函數(shù)作為參數(shù)
inOrderTraverseNode(node, callback) {
// 首先要檢查以參數(shù)形式傳入的節(jié)點(diǎn)是否為 null, 停止遞歸繼續(xù)執(zhí)行的判斷條件
if (node != null) {
// 遞歸調(diào)用相同的函數(shù)來訪問左側(cè)子節(jié)點(diǎn), 再訪問右側(cè)子節(jié)點(diǎn)
this.inOrderTraverseNode(node.left, callback);
callback(node.key);
this.inOrderTraverseNode(node.right, callback);
}
}
// 先序遍歷
preOrderTraveser(callback) {
this.preOrderTraveserNode(this.root, callback);
}
preOrderTraveserNode(node, callback) {
if (node != null) {
callback(node.key);
this.preOrderTraveserNode(node.left, callback);
this.preOrderTraveserNode(node.right, callback);
}
}
// 后序遍歷
postOrderTraverse(callback) {
this.postOrderTraverseNode(this.root, callback);
}
postOrderTraverseNode(node, callback) {
if (node != null) {
// 后序遍歷會先訪問左側(cè)子節(jié)點(diǎn)
this.postOrderTraverseNode(node.left, callback);
// 然后是右側(cè)子節(jié)點(diǎn)
this.postOrderTraverseNode(node.right, callback);
// 最后是父節(jié)點(diǎn)本身
callback(node.key);
}
}
min() {
return this.minNode(this.root);
}
// 允許我們從樹中任意一個節(jié)點(diǎn)開始尋找最小的鍵, 找到最左端
minNode(node) {
let current = node;
while (current != null && current.left != null) {
current = current.left;
}
return current;
}
max() {
return this.maxNode(this.root);
}
// 沿著樹的右邊進(jìn)行遍歷
maxNode(node) {
let current = node;
while (current != null && current.right != null) {
current = current.right;
}
return current;
}
// 聲明 search 方法曹宴。和 BST 中聲明的其他方法的模式相同搂橙，我們將會使用一個輔助方法
search(key) {
return this.searchNode(this.root, key);
}
// searchNode 方法可以用來尋找一棵樹或其任意子樹中的一個特定的值
searchNode(node, key) {
// 驗證作為參數(shù)傳入的 node 是否合法
if (node == null) return false;
// 要找的鍵比當(dāng)前的節(jié)點(diǎn)小, 在左側(cè)的子樹上搜索
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
return this.searchNode(node.left, key);
// 要找的鍵比當(dāng)前的節(jié)點(diǎn)大, 從右側(cè)子節(jié)點(diǎn)開始繼續(xù)搜索
} else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
return this.searchNode(node.right, key);
} else {
return true;
}
}
remove(key) {
// 傳入 root 和要移除的鍵作為參數(shù)
this.root = this.removeNode(this.root, key);
}
removeNode(node, key) {
// 正在檢測的節(jié)點(diǎn)為 null，那么說明鍵不存在于樹中笛坦，所以返回 null
if (node == null) return null;
// 要找的鍵比當(dāng)前節(jié)點(diǎn)的值小, 沿著樹的左邊找到下一個節(jié)點(diǎn)
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
node.left = this.removeNode(node.left, key);
return node;
// 要找的鍵比當(dāng)前節(jié)點(diǎn)的值大, 沿著樹的右邊找到下一個節(jié)點(diǎn)
} else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
node.right = this.removeNode(node.right, key);
return node;
} else {
// 找到了要找的鍵（鍵和 node.key 相等）区转，就需要處理三種不同的情況
// 第一種情況是該節(jié)點(diǎn)是一個沒有左側(cè)或右側(cè)子節(jié)點(diǎn)的葉節(jié)點(diǎn)
if (node.left == null && node.right == null) {
// 是給這個節(jié)點(diǎn)賦予 null 值來移除它
node = null;
// 需要處理引用（指針）。在這里版扩，這個節(jié)點(diǎn)沒有任何子節(jié)點(diǎn)废离，但是它有一個父節(jié)點(diǎn)，需要通過返回 null 來將對應(yīng)的父節(jié)點(diǎn)指針賦予 null 值
return node;
}
// 第二種情況移除有一個左側(cè)子節(jié)點(diǎn)或右側(cè)子節(jié)點(diǎn)的節(jié)點(diǎn), 需要跳過這個節(jié)點(diǎn)礁芦，直接將父節(jié)點(diǎn)指向它的指針指向子節(jié)點(diǎn)
// 這個節(jié)點(diǎn)沒有左側(cè)子節(jié)點(diǎn), 也就是說它有一個右側(cè)子節(jié)點(diǎn), 把對它的引用改為對它右側(cè)子節(jié)點(diǎn)的引用, 返回更新后的節(jié)點(diǎn)
if (node.left == null) {
node = node.right;
return node;
} else if (node.right == null) {
node = node.left;
return node;
}
// 第三種情況, 要移除的節(jié)點(diǎn)有兩個子節(jié)點(diǎn)——左側(cè)子節(jié)點(diǎn)和右側(cè)子節(jié)點(diǎn)
// 當(dāng)找到了要移除的節(jié)點(diǎn)后蜻韭，需要找到它右邊子樹中最小的節(jié)點(diǎn)
const aux = this.minNode(node.right);
// 用它右側(cè)子樹中最小節(jié)點(diǎn)的鍵去更新這個節(jié)點(diǎn)的值, 通過這一步，我們改變了這個節(jié)點(diǎn)的鍵，也就是說它被移除了
node.key = aux.key;
// 這樣在樹中就有兩個擁有相同鍵的節(jié)點(diǎn)了湘捎，這是不行的诀豁。要繼續(xù)把右側(cè)子樹中的最小節(jié)點(diǎn)移除，畢竟它已經(jīng)被移至要移除的節(jié)點(diǎn)的位置了
node.right = this.removeNode(node.right, aux.key);
// 向它的父節(jié)點(diǎn)返回更新后節(jié)點(diǎn)的引用
return node;
}
}
}
移除一個葉節(jié)點(diǎn)
只有一個子節(jié)點(diǎn)
移除兩個節(jié)點(diǎn)
自平衡樹
BST 存在一個問題：取決于你添加的節(jié)點(diǎn)數(shù)窥妇，樹的一條邊可能會非常深舷胜；也就是說，樹的一條分支會有很多層活翩，而其他的分支卻只有幾層, 如下圖
BST
在需要在某條邊上添加烹骨、移除和搜索某個節(jié)點(diǎn)時引起一些性能問題。為了解決這個問題材泄，有一種樹叫作 Adelson-Velskii-Landi 樹（AVL 樹）AVL 是一種自平衡二叉搜索樹, 意思是任何一個節(jié)點(diǎn)左右兩側(cè)子樹的高度之差最多為 1
后續(xù)繼續(xù)更新, 先熟悉一下
