python數據結構與算法-17

二叉查找樹(BST)

二叉樹的一種應用就是來實現堆，今天我們再看看用二叉查找樹(Binary Search Tree, BST)。
前面有章節說到了查找操作，包括線性查找、二分查找、哈希查找等，線性查找效率比較低，二分又要求必須是有序的序列，
為了維持有序插入的代價比較高、哈希查找效率很高但是浪費空間。能不能有一種插入和查找都比較快的數據結構呢？二叉查找樹就是這樣一種結構，可以高效地插入和查詢節點。

BST 定義

二叉查找樹是這樣一種二叉樹結構，它的每個節點包含一個 key 和它附帶的數據，對于每個內部節點 V：

所有 key 小于 V 的都被存儲在 V 的左子樹
所有 key 大于 V 的都存儲在 V 的右子樹

在這里插入圖片描述

注意這個限制條件，可別和堆搞混了。說白了就是對于每個內部節點，左子樹的 key 都比它小，右子樹都比它大。
如果中序遍歷(二叉樹遍歷講過了)這顆二叉樹，你會發現輸出的順序正好是有序的。
我們先來定義一下 BST 的節點結構：

class BSTNode(object):def __init__(self, key, value, left=None, right=None):self.key, self.value, self.left, self.right = key, value, left, right

構造一個 BST

我們還像之前構造二叉樹一樣，按照上圖構造一個 BST 用來演示：

class BST(object):def __init__(self, root=None):self.root = root@classmethoddef build_from(cls, node_list):cls.size = 0key_to_node_dict = {}for node_dict in node_list:key = node_dict['key']key_to_node_dict[key] = BSTNode(key, value=key)   # 這里值暫時用 和 key一樣的for node_dict in node_list:key = node_dict['key']node = key_to_node_dict[key]if node_dict['is_root']:root = nodenode.left = key_to_node_dict.get(node_dict['left'])node.right = key_to_node_dict.get(node_dict['right'])cls.size += 1return cls(root)NODE_LIST = [{'key': 60, 'left': 12, 'right': 90, 'is_root': True},{'key': 12, 'left': 4, 'right': 41, 'is_root': False},{'key': 4, 'left': 1, 'right': None, 'is_root': False},{'key': 1, 'left': None, 'right': None, 'is_root': False},{'key': 41, 'left': 29, 'right': None, 'is_root': False},{'key': 29, 'left': 23, 'right': 37, 'is_root': False},{'key': 23, 'left': None, 'right': None, 'is_root': False},{'key': 37, 'left': None, 'right': None, 'is_root': False},{'key': 90, 'left': 71, 'right': 100, 'is_root': False},{'key': 71, 'left': None, 'right': 84, 'is_root': False},{'key': 100, 'left': None, 'right': None, 'is_root': False},{'key': 84, 'left': None, 'right': None, 'is_root': False},
]
bst = BST.build_from(NODE_LIST)

BST 操作

查找

如何查找一個指定的節點呢，根據定義我們知道每個內部節點左子樹的 key 都比它小，右子樹的 key 都比它大，所以
對于帶查找的節點 search_key，從根節點開始，如果 search_key 大于當前 key，就去右子樹查找，否則去左子樹查找。一直到當前節點是 None 了說明沒找到對應 key。

在這里插入圖片描述

好，擼代碼：

    def _bst_search(self, subtree, key):if subtree is None:   # 沒找到return Noneelif key < subtree.key:return self._bst_search(subtree.left, key)elif key > subtree.key:return self._bst_search(subtree.right, key)else:return subtreedef get(self, key, default=None):node = self._bst_search(self.root, key)if node is None:return defaultelse:return node.value

獲取最大和最小 key 的節點

其實還按照其定義，最小值就一直向著左子樹找，最大值一直向右子樹找，遞歸查找就行。

    def _bst_min_node(self, subtree):if subtree is None:return Noneelif subtree.left is None:   # 找到左子樹的頭return subtreeelse:return self._bst_min_node(subtree.left)def bst_min(self):node = self._bst_min_node(self.root)return node.value if node else None

插入

插入節點的時候我們需要一直保持 BST 的性質，每次插入一個節點，我們都通過遞歸比較把它放到正確的位置。
你會發現新節點總是被作為葉子結點插入。（請你思考這是為什么）
在這里插入圖片描述

    def _bst_insert(self, subtree, key, value):""" 插入并且返回根節點:param subtree::param key::param value:"""if subtree is None:   # 插入的節點一定是根節點，包括 root 為空的情況subtree = BSTNode(key, value)elif key < subtree.key:subtree.left = self._bst_insert(subtree.left, key, value)elif key > subtree.key:subtree.right = self._bst_insert(subtree.right, key, value)return subtreedef add(self, key, value):node = self._bst_search(self.root, key)if node is not None:   # 更新已經存在的 keynode.value = valuereturn Falseelse:self.root = self._bst_insert(self.root, key, value)self.size += 1return True

刪除節點

刪除操作相比上邊的操作要麻煩很多，首先需要定位一個節點，刪除節點后，我們需要始終保持 BST 的性質。
刪除一個節點涉及到三種情況：

節點是葉節點
節點有一個孩子
節點有兩個孩子

我們分別來看看三種情況下如何刪除一個節點：

刪除葉節點

這是最簡單的一種情況，只需要把它的父親指向它的指針設置為 None 就好。

在這里插入圖片描述

刪除只有一個孩子的節點

刪除有一個孩子的節點時，我們拿掉需要刪除的節點，之后把它的父親指向它的孩子就行，因為根據 BST
左子樹都小于節點，右子樹都大于節點的特性，刪除它之后這個條件依舊滿足。

在這里插入圖片描述

刪除有兩個孩子的內部節點

假如我們想刪除 12 這個節點改怎么做呢？你的第一反應可能是按照下圖的方式：
在這里插入圖片描述

但是這種方式可能會影響樹的高度，降低查找的效率。這里我們用另一種非常巧妙的方式。
還記得上邊提到的嗎，如果你中序遍歷 BST 并且輸出每個節點的 key，你會發現就是一個有序的數組。
[1 4 12 23 29 37 41 60 71 84 90 100]。這里我們定義兩個概念，邏輯前任(predecessor)和后繼(successor)，請看下圖:

在這里插入圖片描述

12 在中序遍歷中的邏輯前任和后繼分別是 4 和 23 節點。于是我們還有一種方法來刪除 12 這個節點：

找到待刪除節點 N(12) 的后繼節點 S(23)
復制節點 S 到節點 N
從 N 的右子樹中刪除節點 S，并更新其刪除后繼節點后的右子樹

說白了就是找到后繼并且替換，這里之所以能保證這種方法是正確的，你會發現替換后依舊是保持了 BST 的性質。
有個問題是如何找到后繼節點呢？待刪除節點的右子樹的最小的節點不就是后繼嘛，上邊我們已經實現了找到最小 key 的方法了。

在這里插入圖片描述

我們開始編寫代碼實現，和之前的操作類似，我們還是通過輔助函數的形式來實現，這個遞歸函數會比較復雜，請你仔細理解:

    def _bst_remove(self, subtree, key):"""刪除節點并返回根節點"""if subtree is None:return Noneelif key < subtree.key:subtree.left = self._bst_remove(subtree.left, key)return subtreeelif key > subtree.key:subtree.right = self._bst_remove(subtree.right, key)return subtreeelse:  # 找到了需要刪除的節點if subtree.left is None and subtree.right is None:    # 葉節點，返回 None 把其父親指向它的指針置為 Nonereturn Noneelif subtree.left is None or subtree.right is None:  # 只有一個孩子if subtree.left is not None:return subtree.left   # 返回它的孩子并讓它的父親指過去else:return subtree.rightelse:  # 倆孩子，尋找后繼節點替換，并從待刪節點的右子樹中刪除后繼節點successor_node = self._bst_min_node(subtree.right)subtree.key, subtree.value = successor_node.key, successor_node.valuesubtree.right = self._bst_remove(subtree.right, successor_node.key)return subtreedef remove(self, key):assert key in selfself.size -= 1return self._bst_remove(self.root, key)

完整代碼你可以在本章的 bst.py 找到。
另外推薦一個可以在線演示過程的網址大家可以手動執行下看看效果： https://www.cs.usfca.edu/~galles/visualization/BST.html

時間復雜度分析

上邊介紹的操作時間復雜度和二叉樹的形狀有關。平均來說時間復雜度是和樹的高度成正比的，樹的高度 h 是 log(n)，
但是最壞情況下以上操作的時間復雜度都是 O(n)。為了改善 BST 有很多變種，感興趣請參考延伸閱讀中的內容。

在這里插入圖片描述

源碼

# -*- coding: utf-8 -*-class BSTNode(object):def __init__(self, key, value, left=None, right=None):self.key, self.value, self.left, self.right = key, value, left, rightclass BST(object):def __init__(self, root=None):self.root = root@classmethoddef build_from(cls, node_list):cls.size = 0key_to_node_dict = {}for node_dict in node_list:key = node_dict['key']key_to_node_dict[key] = BSTNode(key, value=key)   # 這里值暫時用 和 key一樣的for node_dict in node_list:key = node_dict['key']node = key_to_node_dict[key]if node_dict['is_root']:root = nodenode.left = key_to_node_dict.get(node_dict['left'])node.right = key_to_node_dict.get(node_dict['right'])cls.size += 1return cls(root)def _bst_search(self, subtree, key):if subtree is None:   # 沒找到return Noneelif key < subtree.key:return self._bst_search(subtree.left, key)elif key > subtree.key:return self._bst_search(subtree.right, key)else:return subtreedef __contains__(self, key):"""實現 in 操作符"""return self._bst_search(self.root, key) is not Nonedef get(self, key, default=None):node = self._bst_search(self.root, key)if node is None:return defaultelse:return node.valuedef _bst_min_node(self, subtree):if subtree is None:return Noneelif subtree.left is None:   # 找到左子樹的頭return subtreeelse:return self._bst_min_node(subtree.left)def bst_min(self):node = self._bst_min_node(self.root)return node.value if node else Nonedef _bst_insert(self, subtree, key, value):""" 插入并且返回根節點:param subtree::param key::param value:"""if subtree is None:   # 插入的節點一定是根節點，包括 root 為空的情況subtree = BSTNode(key, value)elif key < subtree.key:subtree.left = self._bst_insert(subtree.left, key, value)elif key > subtree.key:subtree.right = self._bst_insert(subtree.right, key, value)return subtreedef add(self, key, value):node = self._bst_search(self.root, key)if node is not None:   # 更新已經存在的 keynode.value = valuereturn Falseelse:self.root = self._bst_insert(self.root, key, value)self.size += 1return Truedef _bst_remove(self, subtree, key):"""刪除節點并返回根節點"""if subtree is None:return Noneelif key < subtree.key:subtree.left = self._bst_remove(subtree.left, key)return subtreeelif key > subtree.key:subtree.right = self._bst_remove(subtree.right, key)return subtreeelse:  # 找到了需要刪除的節點if subtree.left is None and subtree.right is None:    # 葉節點，返回 None 把其父親指向它的指針置為 Nonereturn Noneelif subtree.left is None or subtree.right is None:  # 只有一個孩子if subtree.left is not None:return subtree.left   # 返回它的孩子并讓它的父親指過去else:return subtree.rightelse:  # 倆孩子，尋找后繼節點替換，并刪除其右子樹的后繼節點，同時更新其右子樹successor_node = self._bst_min_node(subtree.right)subtree.key, subtree.value = successor_node.key, successor_node.valuesubtree.right = self._bst_remove(subtree.right, successor_node.key)return subtreedef remove(self, key):assert key in selfself.size -= 1return self._bst_remove(self.root, key)NODE_LIST = [{'key': 60, 'left': 12, 'right': 90, 'is_root': True},{'key': 12, 'left': 4, 'right': 41, 'is_root': False},{'key': 4, 'left': 1, 'right': None, 'is_root': False},{'key': 1, 'left': None, 'right': None, 'is_root': False},{'key': 41, 'left': 29, 'right': None, 'is_root': False},{'key': 29, 'left': 23, 'right': 37, 'is_root': False},{'key': 23, 'left': None, 'right': None, 'is_root': False},{'key': 37, 'left': None, 'right': None, 'is_root': False},{'key': 90, 'left': 71, 'right': 100, 'is_root': False},{'key': 71, 'left': None, 'right': 84, 'is_root': False},{'key': 100, 'left': None, 'right': None, 'is_root': False},{'key': 84, 'left': None, 'right': None, 'is_root': False},
]def test_bst_tree():bst = BST.build_from(NODE_LIST)for node_dict in NODE_LIST:key = node_dict['key']assert bst.get(key) == keyassert bst.size == len(NODE_LIST)assert bst.get(-1) is None    # 單例的 None 我們用 is 來比較assert bst.bst_min() == 1bst.add(0, 0)assert bst.bst_min() == 0bst.remove(12)assert bst.get(12) is Nonebst.remove(1)assert bst.get(1) is Nonebst.remove(29)assert bst.get(29) is None