1. 定義
設(shè) x 是BST中的一個節(jié)點,
若 y 是 x 的左子樹中的任一節(jié)點, 則 y.data x.data ;
若 y 是 x 的右子樹中的任一節(jié)點, 則 y.data x.data .
由定義可知, 對BST進行中序遍歷可得到一個有序數(shù)列.
首先定義BST的節(jié)點: 除左右孩子外, 還包含一個指向父親節(jié)點的指針.
class BSTNode(object):
def __init__(self, data=None, left=None, right=None, p=None):
self.data = data
self.left = left
self.right = right
self.p = p
2. 插入
- 從根節(jié)點開始逐層比較, 找到合適的葉節(jié)點 pre 作為待插節(jié)點 x 的父親節(jié)點.
- 特殊情況: 空樹. 此時將 x 作為根節(jié)點即可.
class BinarySearchTree(AbstractCollection):
def __init__(self, source_collection=None):
self._root = None
super().__init__(source_collection)
# 1. 插入
def add(self, data):
x = BSTNode(data)
self._insert(x)
def _insert(self, x):
pre, probe = None, self._root
while probe != None:
pre = probe
if x.data < probe.data:
probe = probe.left
else:
probe = probe.right
x.p = pre
if pre is None:
self._root = x
elif x.data < pre.data:
pre.left = x
else:
pre.right = x
self._size += 1
3. 遍歷
- 深度遍歷(前中后序): 遞歸實現(xiàn).
- 廣度遍歷(層級): 借助輔助隊列, 實現(xiàn)逐層(從左至右)遍歷. 關(guān)于鏈?zhǔn)疥犃泻蜅５膶崿F(xiàn), 參考此文.
- iter實現(xiàn)為前序遍歷的非遞歸版本.
# 2. 遍歷
def inorder_tree_walk(self, x=False):
if x is False:
x = self._root
if x is not None:
yield from self.inorder_tree_walk(x.left)
yield x.data
yield from self.inorder_tree_walk(x.right)
def preorder_tree_walk(self, x=False):
if x is False:
x = self._root
if x is not None:
yield x.data
yield from self.inorder_tree_walk(x.left)
yield from self.inorder_tree_walk(x.right)
def postorder_tree_walk(self, x=False):
if x is False:
x = self._root
if x is not None:
yield from self.inorder_tree_walk(x.left)
yield from self.inorder_tree_walk(x.right)
yield x.data
def levelorder_tree_walk(self):
if self.is_empty():
return
queue = LinkedQueue()
queue.add(self._root)
while not queue.is_empty():
node = queue.pop()
yield node.data
if node.left != None:
queue.add(node.left)
if node.right != None:
queue.add(node.right)
def __iter__(self):
if self.is_empty():
return
stack = LinkedStack()
stack.push(self._root)
while not stack.is_empty():
node = stack.pop()
yield node.data
if node.right != None:
stack.push(node.right)
if node.left != None:
stack.push(node.left)
4. 查找
- 最值: 最小值位于最左邊節(jié)點, 最大值位于最右邊節(jié)點.
- 后繼: 若有右子樹, 則返回右子樹中的最小節(jié)點; 否則, 迭代的尋找某個祖先節(jié)點, 直至滿足當(dāng)前節(jié)點是其父節(jié)點的左孩子, 返回父節(jié)點.
- 前驅(qū): 與尋找后繼節(jié)點的算法完全對稱.
# 3. 查找: in, max, min, successor, predecessor
def __contains__(self, data):
return self._find(data) != None
def max_data(self):
return self._max(self._root).data
def min_data(self):
return self._min(self._root).data
def _min(self, node):
if self.is_empty():
raise KeyError('The tree is empty.')
while node.left != None:
node = node.left
return node
def _max(self, node):
if self.is_empty():
raise KeyError('The tree is empty.')
while node.right != None:
node = node.right
return node
def _find(self, data):
probe = self._root
while probe != None and probe.data != data:
if data < probe.data:
probe = probe.left
else:
probe = probe.right
return probe
def _successor(self, x):
"""找某個節(jié)點的后繼: 若有右子樹, 則返回其右子樹的最小節(jié)點; 否則, 迭代找其某個祖先節(jié)點, 直至滿足當(dāng)前節(jié)點是其父的left, 返回其父"""
if x.right != None:
return self._min(x.right)
else:
y = x.p
while y != None and x != y.left:
x = y
y = y.p
return y
def _predecessor(self, x):
"""找某個節(jié)點的前驅(qū): _successor的對稱操作"""
if x.left != None:
return self._max(x.left)
else:
y = x.p
while y != None and x != y.right:
x = y
y = y.p
return y
5. 刪除
Case 1: x 沒有孩子節(jié)點, 直接刪除.
Case 2: x 僅有一個孩子(子樹), 將該子樹上移替換掉 x .
-
Case 3: x 有兩個孩子, 在子樹 x.right 中找到 x 的后繼節(jié)點 y (顯然 y 沒有左孩子), 讓 y 占據(jù) x 的位置. 此時可能出現(xiàn)兩種情況:
(1) y 是 x 的右孩子. 此時直接將 y 上移替換掉 x .
(2) y 非 x 的右孩子. 此時取出 y , 將 y 的右孩子上移至 y 的位置, 然后取出子樹 x.right , 并讓其成為 y 的右孩子, 演變成情形(1), 重復(fù)(1)的操作. 如圖所示:
(1) y.p == x
(2) y.p != x 子樹替換子程序_tranplant(u, v): 用子樹 v 替換子樹 u .
# 4. 刪除
def remove(self, data):
x = self._find(data)
if x is None:
raise KeyError("Data is not in the tree.")
if x.left is None:
self._transplant(x, x.right)
elif x.right is None:
self._transplant(x, x.left)
else:
y = self._successor(x)
if y.p != x: # (2)
self._transplant(y, y.right)
y.right = x.right
y.right.p = y
self._transplant(x, y)
y.left = x.left
y.left.p = y
def _transplant(self, u, v):
if u.p is None:
self._root = v
elif u is u.p.left:
u.p.left = v
else:
u.p.right = v
if v != None:
v.p = u.p
6. 時間復(fù)雜度
遍歷的時間復(fù)雜度是 .
插入刪除查找的時間復(fù)雜度都是 .
建樹的時間復(fù)雜度是 .
其中 n 是節(jié)點總數(shù), h是樹的高度, 顯然,
所以普通的二叉搜索樹并不能保證 logn 級的查找速度.
另外, 快速排序的過程可以想象成構(gòu)建一棵二叉搜索樹, 故復(fù)雜度等價.
