建站
咨詢
售后
建站咨詢
新聞中心
二叉排序樹
二叉排序樹又稱為二叉查找樹。它或者是一顆空樹，或者是具有下列性質(zhì)的二叉樹：
若它的左子樹不為空，則左子樹上所有節(jié)點的值均小于它的根結(jié)構(gòu)的值；若它的右子樹不為空，則右子樹上所有節(jié)點的值均大于它的根結(jié)構(gòu)的值；它的左、右子樹也分別為二叉排序樹。
構(gòu)造一顆二叉排序樹的目的，往往不是為了排序，而是為了提高查找和插入刪除關(guān)鍵字的速度。
二叉排序樹的操作：
查找：對比節(jié)點的值和關(guān)鍵字，相等則表明找到了；小了則往節(jié)點的左子樹去找，大了則往右子樹去找，這么遞歸下去，最后返回布爾值或找到的節(jié)點。插入：從根節(jié)點開始逐個與關(guān)鍵字進行對比，小了去左邊，大了去右邊，碰到子樹為空的情況就將新的節(jié)點鏈接。刪除：如果要刪除的節(jié)點是葉子，直接刪；如果只有左子樹或只有右子樹，則刪除節(jié)點后，將子樹鏈接到父節(jié)點即可；如果同時有左右子樹，則可以將二叉排序樹進行中序遍歷，取將要被刪除的節(jié)點的前驅(qū)或者后繼節(jié)點替代這個被刪除的節(jié)點的位置。
"""
定義一個二叉樹節(jié)點類。
以討論算法為主，忽略了一些諸如對數(shù)據(jù)類型進行判斷的問題。
"""
def __init__(self, data, left=None, right=None):
"""
初始化
:param data: 節(jié)點儲存的數(shù)據(jù)
:param left: 節(jié)點左子樹
:param right: 節(jié)點右子樹
"""
self.data = data
self.left = left
self.right = rightclass BinarySortTree:
"""
基于BSTNode類的二叉排序樹。維護一個根節(jié)點的指針。
"""
def __init__(self):
self._root = None
def is_empty(self):
return self._root is None
def search(self, key):
"""
關(guān)鍵碼檢索
:param key: 關(guān)鍵碼
:return: 查詢節(jié)點或None
"""
bt = self._root while bt:
entry = bt.data if key < entry:
bt = bt.left elif key > entry:
bt = bt.right else: return entry return None
def insert(self, key):
"""
插入操作
:param key:關(guān)鍵碼
:return: 布爾值
"""
bt = self._root if not bt:
self._root = BSTNode(key) return
while True:
entry = bt.data if key < entry: if bt.left is None:
bt.left = BSTNode(key) return
bt = bt.left elif key > entry: if bt.right is None:
bt.right = BSTNode(key) return
bt = bt.right else:
bt.data = key return
def delete(self, key):
"""
二叉排序樹最復雜的方法
:param key: 關(guān)鍵碼
:return: 布爾值
"""
p, q = None, self._root # 維持p為q的父節(jié)點，用于后面的鏈接操作
if not q:
print("空樹！") return
while q and q.data != key:
p = q if key < q.data:
q = q.left else:
q = q.right if not q: # 當樹中沒有關(guān)鍵碼key時，結(jié)束退出。
return
# 上面已將找到了要刪除的節(jié)點，用q引用。而p則是q的父節(jié)點或者None（q為根節(jié)點時）。
if not q.left: if p is None:
self._root = q.right elif q is p.left:
p.left = q.right else:
p.right = q.right return
# 查找節(jié)點q的左子樹的最右節(jié)點，將q的右子樹鏈接為該節(jié)點的右子樹
# 該方法可能會增大樹的深度，效率并不算高。可以設(shè)計其它的方法。
r = q.left while r.right:
r = r.right
r.right = q.right if p is None:
self._root = q.left elif p.left is q:
p.left = q.left else:
p.right = q.left def __iter__(self):
"""
實現(xiàn)二叉樹的中序遍歷算法,
展示我們創(chuàng)建的二叉排序樹.
直接使用python內(nèi)置的列表作為一個棧。
:return: data
"""
stack = []
node = self._root while node or stack: while node:
stack.append(node)
node = node.left
node = stack.pop() yield node.data
node = node.rightif __name__ == '__main__':
lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]
bs_tree = BinarySortTree() for i in range(len(lis)):
bs_tree.insert(lis[i]) # bs_tree.insert(100)
bs_tree.delete(58) for i in bs_tree:
print(i, end=" ") # print("\n", bs_tree.search(4))相關(guān)推薦：《Python視頻教程》
二叉排序樹總結(jié)：
二叉排序樹以鏈式進行存儲，保持了鏈接結(jié)構(gòu)在插入和刪除操作上的優(yōu)點。在極端情況下，查詢次數(shù)為1，但操作次數(shù)不會超過樹的深度。也就是說，二叉排序樹的查找性能取決于二叉排序樹的形狀，也就引申出了后面的平衡二叉樹。給定一個元素集合，可以構(gòu)造不同的二叉排序樹，當它同時是一個完全二叉樹的時候，查找的時間復雜度為O(log(n))，近似于二分查找。當出現(xiàn)最極端的斜樹時，其時間復雜度為O(n)，等同于順序查找，效果最差。
平衡二叉樹
平衡二叉樹（AVL樹，發(fā)明者的姓名縮寫）：一種高度平衡的排序二叉樹，其每一個節(jié)點的左子樹和右子樹的高度差最多等于1。
平衡二叉樹首先必須是一棵二叉排序樹！
平衡因子（Balance Factor）：將二叉樹上節(jié)點的左子樹深度減去右子樹深度的值。
對于平衡二叉樹所有包括分支節(jié)點和葉節(jié)點的平衡因子只可能是-1,0和1，只要有一個節(jié)點的因子不在這三個值之內(nèi)，該二叉樹就是不平衡的。
最小不平衡子樹：距離插入結(jié)點最近的，且平衡因子的絕對值大于1的節(jié)點為根的子樹。
平衡二叉樹的構(gòu)建思想：每當插入一個新結(jié)點時，先檢查是否破壞了樹的平衡性，若有，找出最小不平衡子樹。在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的連接關(guān)系，進行相應(yīng)的旋轉(zhuǎn)，成為新的平衡子樹。
下面是由[1,2,3,4,5,6,7,10,9]構(gòu)建平衡二叉樹
網(wǎng)站標題：創(chuàng)新互聯(lián)Python教程：Python中的二叉排序樹和平衡二叉樹是什么
當前路徑：http://www.dlmjj.cn/article/dhgopec.html
