Python數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的定義、查找、插入、構(gòu)造、刪除
本篇章主要介紹二叉樹的應用之一------二叉排序樹，包括二叉排序樹的定義、查找、插入、構(gòu)造、刪除及查找效率分析。
1. 二叉排序樹的定義
二叉排序樹 ( B i n a r y (Binary (Binary S o r t Sort Sort T r e e , B S T ) Tree,BST) Tree,BST)，也稱為二叉查找樹，具有以下性質(zhì)：
(1) 若左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；
(2) 若右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；
(3) 左、右子樹也分別是一棵二叉排序樹。
綜上可知，在二叉排序樹中：左子樹結(jié)點的值 < 根結(jié)點的值 < 右子樹結(jié)點的值，所以對二叉排序樹進行中序遍歷，可以得到一個遞增的有序序列。
2. 二叉排序樹的查找
二叉排序樹的查找是從根結(jié)點開始，沿某個分支逐層向下比較的過程。若二叉排序樹非空，先將給定的關(guān)鍵字與根結(jié)點的關(guān)鍵字進行比較，若相等，則查找成功；若不相等，如果小于根結(jié)點的關(guān)鍵字，則在根結(jié)點的左子樹上查找，如果大于根結(jié)點的關(guān)鍵字，則在根結(jié)點的右子樹上查找。
二叉排序樹的查找算法：
def BSTSearch(self, k): TreeNode = self.RootNode while TreeNode is not None and k != TreeNode.data: if k < TreeNode.data: TreeNode = TreeNode.lchild else: TreeNode = TreeNode.rchild return TreeNode
3. 二叉排序樹的插入
二叉排序樹作為一種動態(tài)樹表，它的結(jié)構(gòu)通常不是一次生成的，而是在查找過程中，當樹中不存在關(guān)鍵字等于給定值的結(jié)點時插入的。
插入過程如下：若二叉排序樹為空，則直接插入結(jié)點；若非空，先將給定的關(guān)鍵字與根結(jié)點的關(guān)鍵字進行比較，若小于根結(jié)點的關(guān)鍵字，則插入左子樹，若大于根結(jié)點的關(guān)鍵字，則插入右子樹。插入的結(jié)點一定是一個新添加的葉結(jié)點，且是查找失敗時的查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子。
二叉排序樹的插入算法：
def BSTInsert(self, k): TreeNode = self.RootNode if TreeNode is None: self.RootNode = BiTreeLinkNode(k) return True while True: if k < TreeNode.data: if TreeNode.lchild is None: TreeNode.lchild = BiTreeLinkNode(k) return True TreeNode = TreeNode.lchild elif k > TreeNode.data: if TreeNode.rchild is None: TreeNode.rchild = BiTreeLinkNode(k) return True TreeNode = TreeNode.rchild else: return False
4. 二叉排序樹的構(gòu)造
二叉排序樹的構(gòu)造過程如下：從一棵空樹出發(fā)，依次輸入元素，將它們插入樹中的合適位置。關(guān)鍵字的序列不同，構(gòu)造出來的二叉排序樹也會有所不同，比如下圖：
二叉排序樹的構(gòu)造算法：
def CreateBST(self): for val in self.data_list: self.BSTInsert(val) return self.RootNode
5. 二叉排序樹的刪除
在二叉排序樹中刪除一個結(jié)點時，不能把以該結(jié)點為根的子樹上的結(jié)點都刪除，必須先把被刪除的結(jié)點從存儲二叉排序樹的鏈表上摘下，將因刪除結(jié)點而斷開的二叉鏈表重新連接起來，同時確保二叉排序樹的性質(zhì)不會丟失。具體分三種情況：
(1) 如果被刪除的結(jié)點是葉結(jié)點，可以直接刪除；
(2) 如果被刪除的結(jié)點只有一棵左子樹或右子樹，需要讓該結(jié)點的子樹成為該結(jié)點的父結(jié)點的子樹，以替代被刪除結(jié)點的位置；
(3) 被刪除的結(jié)點有左子樹和右子樹，需要用該結(jié)點的直接后繼來代替該結(jié)點的位置，然后從二叉排序樹中刪去這個直接后繼。
6. 二叉排序樹的查找效率分析
如果二叉排序樹的左、右子樹的高度之差的絕對值不超過1，則這樣的二叉樹稱為平衡二叉樹，它的平均查找長度為 O ( l o g 2 n ) O(log_2n) O(log2n)；如果二叉排序樹是一個只有左子樹或右子樹的單支樹(類似于有序的單鏈表)，則它的平均查找長度為 O ( n ) 。
在等概率情況下，有序列 { 2 , 1 , 4 , 3 }成的排序二叉樹的查找成功的平均查找長度為
有序列 { 1 , 2 , 3 , 4 } 構(gòu)成的排序二叉樹的查找成功的平均查找長度為
二叉排序樹的查找效率主要取決于樹的高度，如果要提高查找效率，在構(gòu)造二叉排序時最好不要使用有序的序列，盡量構(gòu)造平衡二叉樹。
有關(guān)平均查找長度 A S L ASL ASL的知識會在查找這部分再說。
總結(jié)
到此這篇關(guān)于Python數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的定義、查找、插入、構(gòu)造、刪除的文章就介紹到這了,更多相關(guān)Python二叉排序樹應用內(nèi)容請搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！
版權(quán)聲明：本站文章來源標注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復制或仿造本網(wǎng)站，禁止在非maisonbaluchon.cn所屬的服務器上建立鏡像，否則將依法追究法律責任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學習參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信