二元搜尋樹

二叉查詢樹，也稱為有序二叉樹，是指一棵空樹或者具有下列性質的二叉樹：二叉查詢樹相比於其他資料結構的優勢在於查詢、插入的時間複雜度較低。為formula_1。二叉查詢樹是基礎性資料結構，用於構建更為抽象的資料結構，如集合、多重集、關聯陣列等。二叉查詢樹的查詢過程和次優二叉樹類似，通常採取二叉連結串列作為二叉查詢樹的儲存結構。中序遍歷二叉查詢樹可得到一個關鍵字的有序序列，一個無序序列可以透過建構一棵二叉查詢樹變成一個有序序列，建構樹的過程即為對無序序列進行查詢的過程。每次插入的新的結點都是二叉查詢樹上新的葉子結點，在進行插入操作時，不必移動其它結點，只需改動某個結點的指標，由空變為非空即可。搜尋、插入、刪除的複雜度等於樹高，期望formula_1，最壞退化為偏斜二元樹formula_3。對於可能形成偏斜二元樹的問題可以經由樹高改良後的平衡樹將搜尋、插入、刪除的時間複雜度都維持在formula_1，如AVL樹、紅黑樹等。二叉查詢樹的查詢演算法.在二叉查詢樹b中查詢x的過程為：Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &amp;p) {// 在根指標T所指二叉查詢樹中遞迴地查詢其關鍵字等於key的資料元素，若查詢成功，// 則指標p指向該資料元素節點，並返回TRUE，否則指標指向查詢路徑上訪問的最後// 一個節點並返回FALSE，指標f指向T的雙親，其初始呼叫值為NULLif (!T) { // 查詢不成功p = f;return false;} else if (key == T-&gt;data.key) { // 查詢成功p = T;return true;} else if (key data.key) // 在左子樹中繼續查詢return SearchBST(T-&gt;lchild, key, T, p);else // 在右子樹中繼續查詢return SearchBST(T-&gt;rchild, key, T, p);在二叉查詢樹插入節點的演算法.向一個二元搜尋樹b中插入一個節點s的演算法，過程為：/* 當二元搜尋樹T中不存在關鍵字等於e.key的資料元素時，插入e並返回TRUE，否則返回 FALSE */Status InsertBST(BiTree *&amp;T, ElemType e) {if (!T) {s = new BiTNode;s-&gt;data = e;s-&gt;lchild = s-&gt;rchild = NULL;T = s; // 被插節點*s為新的根結點} else if (e.key == T-&gt;data.key)return false;// 關鍵字等於e.key的資料元素，返回錯誤if (e.key data.key)InsertBST(T-&gt;lchild, e); // 將 e 插入左子樹else if (e.key &gt; T-&gt;data.key)InsertBST(T-&gt;rchild, e); // 將 e 插入右子樹return true;在二叉查詢樹刪除結點的演算法.在二叉查詢樹刪去一個結點，分三種情況討論：在二叉查詢樹上刪除一個結點的演算法如下：Status DeleteBST(BiTree *T, KeyType key) {// 若二叉查詢樹T中存在關鍵字等於key的資料元素時，則刪除該資料元素，並返回// TRUE；否則返回FALSEif (!T)return false; //不存在關鍵字等於key的資料元素else {if (key == T-&gt;data.key) // 找到關鍵字等於key的資料元素return Delete(T);else if (key data.key)return DeleteBST(T-&gt;lchild, key);elsereturn DeleteBST(T-&gt;rchild, key);Status Delete(BiTree *&amp;p) {// 該節點為葉子節點，直接刪除BiTree *q, *s;if (!p-&gt;rchild &amp;&amp; !p-&gt;lchild) {delete p;p = NULL; // Status Delete(BiTree *&amp;p) 要加&amp;才能使P指向NULL} else if (!p-&gt;rchild) { // 右子樹空則只需重接它的左子樹q = p-&gt;lchild;p-&gt;data = p-&gt;lchild-&gt;data;p-&gt;lchild=p-&gt;lchild-&gt;lchild;p-&gt;rchild=p-&gt;lchild-&gt;rchild;p-&gt;data = q-&gt;data;p-&gt;lchild = q-&gt;lchild;p-&gt;rchild = q-&gt;rchild;delete q;} else if (!p-&gt;lchild) { // 左子樹空只需重接它的右子樹q = p-&gt;rchild;p-&gt;data = p-&gt;rchild-&gt;data;p-&gt;lchild=p-&gt;rchild-&gt;lchild;p-&gt;rchild=p-&gt;rchild-&gt;rchild;p-&gt;data = q-&gt;data;p-&gt;lchild = q-&gt;lchild;p-&gt;rchild = q-&gt;rchild;delete q;} else { // 左右子樹均不空q = p;s = p-&gt;lchild;while (s-&gt;rchild) {q = s;s = s-&gt;rchild;} // 轉左，然後向右到盡頭p-&gt;data = s-&gt;data; // s指向被刪結點的“前驅”if (q != p)q-&gt;rchild = s-&gt;lchild; // 重接*q的右子樹elseq-&gt;lchild = s-&gt;lchild; // 重接*q的左子樹delete s;return true;在C語言中有些編譯器不支援為codice_1 節點分配空間，聲稱這是一個不完全的結構，可使用一個指向該codice_2的指標為之分配空間。Python實現：def find_min(self): # Gets minimum node (leftmost leaf) in a subtreecurrent_node = selfwhile current_node.left_child:current_node = current_node.left_childreturn current_nodedef replace_node_in_parent(self, new_value=None):if self.parent:if self == self.parent.left_child:self.parent.left_child = new_valueelse:self.parent.right_child = new_valueif new_value:new_value.parent = self.parentdef binary_tree_delete(self, key):if key  self.key:self.right_child.binary_tree_delete(key)else: # delete the key hereif self.left_child and self.right_child: # if both children are presentsuccessor = self.right_child.find_min()self.key = successor.keysuccessor.binary_tree_delete(successor.key)elif self.left_child: # if the node has only a *left* childself.replace_node_in_parent(self.left_child)elif self.right_child: # if the node has only a *right* childself.replace_node_in_parent(self.right_child)else: # this node has no childrenself.replace_node_in_parent(None)二叉查詢樹的遍歷.中序遍歷二叉查詢樹的Python程式碼：def traverse_binary_tree(node, callback):if node is None:returntraverse_binary_tree(node.leftChild, callback)callback(node.value)traverse_binary_tree(node.rightChild, callback)排序一棵二叉查詢樹.用一組數值建造一棵二叉查詢樹的同時，也把這組數值進行了排序。其最差時間複雜度為formula_5。例如，若該組數值已經是有序的演算法，保持一個數值序列的有序性。def build_binary_tree(values):tree = Nonefor v in values:tree = binary_tree_insert(tree, v)return treedef get_inorder_traversal(root):Returns a list containing all the values in the tree, starting at *root*.Traverses the tree in-order(leftChild, root, rightChild).result = []traverse_binary_tree(root, lambda element: result.append(element))return result二叉查詢樹效能分析.每個結點的formula_6為該結點的層次數。最壞情況下，當先後插入的關鍵字有序時，構成的二叉查詢樹蛻變為單支樹，樹的深度為formula_7，其平均查詢長度為formula_8。二叉查詢樹的最佳化.一般的二叉查詢樹的查詢複雜度取決於目標結點到樹根的距離，因此當結點的深度普遍較大時，查詢的均攤複雜度會上升。為了實現更高效的查詢，產生了平衡樹。在這裡，平衡指所有葉子的深度趨於平衡，更廣義的是指在樹上所有可能查詢的均攤複雜度偏低。請條目平衡樹。