建站
咨詢
售后
建站咨詢
新聞中心
二叉排序樹
二叉排序樹又稱為二叉查找樹。它或者是一顆空樹，或者是具有下列性質(zhì)的二叉樹：
若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根結(jié)構(gòu)的值；若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根結(jié)構(gòu)的值；它的左、右子樹也分別為二叉排序樹。
構(gòu)造一顆二叉排序樹的目的，往往不是為了排序，而是為了提高查找和插入刪除關(guān)鍵字的速度。
二叉排序樹的操作：
查找：對(duì)比節(jié)點(diǎn)的值和關(guān)鍵字，相等則表明找到了；小了則往節(jié)點(diǎn)的左子樹去找，大了則往右子樹去找，這么遞歸下去，最后返回布爾值或找到的節(jié)點(diǎn)。插入：從根節(jié)點(diǎn)開始逐個(gè)與關(guān)鍵字進(jìn)行對(duì)比，小了去左邊，大了去右邊，碰到子樹為空的情況就將新的節(jié)點(diǎn)鏈接。刪除：如果要?jiǎng)h除的節(jié)點(diǎn)是葉子，直接刪；如果只有左子樹或只有右子樹，則刪除節(jié)點(diǎn)后，將子樹鏈接到父節(jié)點(diǎn)即可；如果同時(shí)有左右子樹，則可以將二叉排序樹進(jìn)行中序遍歷，取將要被刪除的節(jié)點(diǎn)的前驅(qū)或者后繼節(jié)點(diǎn)替代這個(gè)被刪除的節(jié)點(diǎn)的位置。
"""
定義一個(gè)二叉樹節(jié)點(diǎn)類。
以討論算法為主，忽略了一些諸如對(duì)數(shù)據(jù)類型進(jìn)行判斷的問題。
"""
def __init__(self, data, left=None, right=None):
"""
初始化
:param data: 節(jié)點(diǎn)儲(chǔ)存的數(shù)據(jù)
:param left: 節(jié)點(diǎn)左子樹
:param right: 節(jié)點(diǎn)右子樹
"""
self.data = data
self.left = left
self.right = rightclass BinarySortTree:
"""
基于BSTNode類的二叉排序樹。維護(hù)一個(gè)根節(jié)點(diǎn)的指針。
"""
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é)點(diǎn)或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):
"""
二叉排序樹最復(fù)雜的方法
:param key: 關(guān)鍵碼
:return: 布爾值
"""
p, q = None, self._root # 維持p為q的父節(jié)點(diǎn)，用于后面的鏈接操作
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: # 當(dāng)樹中沒有關(guān)鍵碼key時(shí)，結(jié)束退出。
return
# 上面已將找到了要?jiǎng)h除的節(jié)點(diǎn)，用q引用。而p則是q的父節(jié)點(diǎn)或者None（q為根節(jié)點(diǎn)時(shí)）。
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é)點(diǎn)q的左子樹的最右節(jié)點(diǎn)，將q的右子樹鏈接為該節(jié)點(diǎn)的右子樹
# 該方法可能會(huì)增大樹的深度，效率并不算高。可以設(shè)計(jì)其它的方法。
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):
"""
實(shí)現(xiàn)二叉樹的中序遍歷算法,
展示我們創(chuàng)建的二叉排序樹.
直接使用python內(nèi)置的列表作為一個(gè)棧。
: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é)：
二叉排序樹以鏈?zhǔn)竭M(jìn)行存儲(chǔ)，保持了鏈接結(jié)構(gòu)在插入和刪除操作上的優(yōu)點(diǎn)。在極端情況下，查詢次數(shù)為1，但操作次數(shù)不會(huì)超過樹的深度。也就是說，二叉排序樹的查找性能取決于二叉排序樹的形狀，也就引申出了后面的平衡二叉樹。給定一個(gè)元素集合，可以構(gòu)造不同的二叉排序樹，當(dāng)它同時(shí)是一個(gè)完全二叉樹的時(shí)候，查找的時(shí)間復(fù)雜度為O(log(n))，近似于二分查找。當(dāng)出現(xiàn)最極端的斜樹時(shí)，其時(shí)間復(fù)雜度為O(n)，等同于順序查找，效果最差。
平衡二叉樹
平衡二叉樹（AVL樹，發(fā)明者的姓名縮寫）：一種高度平衡的排序二叉樹，其每一個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差最多等于1。
平衡二叉樹首先必須是一棵二叉排序樹！
平衡因子（Balance Factor）：將二叉樹上節(jié)點(diǎn)的左子樹深度減去右子樹深度的值。
對(duì)于平衡二叉樹所有包括分支節(jié)點(diǎn)和葉節(jié)點(diǎn)的平衡因子只可能是-1,0和1，只要有一個(gè)節(jié)點(diǎn)的因子不在這三個(gè)值之內(nèi)，該二叉樹就是不平衡的。
最小不平衡子樹：距離插入結(jié)點(diǎn)最近的，且平衡因子的絕對(duì)值大于1的節(jié)點(diǎn)為根的子樹。
平衡二叉樹的構(gòu)建思想：每當(dāng)插入一個(gè)新結(jié)點(diǎn)時(shí)，先檢查是否破壞了樹的平衡性，若有，找出最小不平衡子樹。在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的連接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，成為新的平衡子樹。
下面是由[1,2,3,4,5,6,7,10,9]構(gòu)建平衡二叉樹
當(dāng)前文章：創(chuàng)新互聯(lián)Python教程：Python中的二叉排序樹和平衡二叉樹是什么
分享地址：http://m.fisionsoft.com.cn/article/dhgopec.html
