您好,登錄后才能下訂單哦!
這篇文章給大家介紹如何解析平衡二叉搜索樹Treap,內容非常詳細,感興趣的小伙伴們可以參考借鑒,希望對大家能有所幫助。
今天和大家聊一個新的數據結構,叫做Treap。
Treap本質上也是一顆BST(平衡二叉搜索樹),和我們之前介紹的SBT是一樣的。但是Treap維持平衡的方法和SBT不太一樣,有些許區別,相比來說呢,Treap的原理還要再簡單一些,所以之前在競賽當中不允許使用STL的時候,我們通常都會手寫一棵Treap來代替。
Treap的基本原理
既然是平衡二叉搜索樹,關鍵點就在于平衡,那么重點自然是如何維護樹的平衡。
在Treap當中,維護平衡非常簡單,只有一句話,就是通過維護小頂堆的形式來維持樹的平衡。Treap也正是因此得名,因為它是Tree和Heap的結合體。
我們來看下Treap當中節點的結構:
class TreapNode(TreeNode): """ TreeNode: The node class of treap tree. Paramters: key: The key of node, can be treated as the key of dictionary value: The value of node, can be treated as the value of dictionary priority: The priority of node, specially for treap structure, describe the priority of the node in the treap. lchild: The left child of node rchild: The right child of node father: The parent of node, incase that we need to remove or rotate the node in the treap, so we need father parameter to mark the address of the parent """ def __init__(self, key=None, value=None, lchild=None, rchild=None, father=None, priority=None): super().__init__(key, value, lchild, rchild, father) self._priority = priority @property def priority(self): return self._priority @priority.setter def priority(self, priority): self._priority = priority def __str__(self): return 'key={}, value={}'.format(self.key, self.value)
這里的TreeNode是我抽象出來的樹結構通用的Node,當中包含key、value、lchild、rchild和father。TreapNode其實就是在此基礎上增加了一個priority屬性。
之所以要增加這個priority屬性是為了維護它堆的性質,通過維護這個堆的性質來保持樹的平衡。具體的操作方法,請往下看。
Treap的增刪改查
插入
首先來講Treap的插入元素的操作,其實插入元素的操作非常簡單,就是普通BST插入元素的操作。唯一的問題是如何維持樹的平衡。
我們前文說了,我們是通過維持堆的性質來保持平衡的,那么自然又會有一個新的問題。為什么維持堆的性質可以保證平衡呢?
答案很簡單,因為我們在插入的時候,需要對每一個插入的Node隨機附上一個priority。堆就是用來維護這個priority的,保證樹根一定擁有最小的priority。正是由于這個priority是隨機的,我們可以保證整棵樹蛻化成線性的概率降到無窮低。
當我們插入元素之后發現破壞了堆的性質,那么我們需要通過旋轉操作來維護。舉個簡單的例子,在下圖當中,如果B節點的priority比D要小,為了保證堆的性質,需要將B和D進行互換。由于直接互換會破壞BST的性質,所以我們采取旋轉的操作。
旋轉之后我們發現B和D互換了位置,并且旋轉之后的A和E的priority都是大于D的,所以旋轉之后我們整棵樹依然維持了性質。
右旋的情況也是一樣的,其實我們觀察一下會發現,要交換左孩子和父親需要右旋,如果是要交換右孩子和父親,則需要左旋。
整個插入的操作其實就是基礎的BST插入過程,加上旋轉的判斷。
def _insert(self, node, father, new_node, left_or_right='left'): """ Inside implement of insert node. Implement in recursion. Since the parameter passed in Python is reference, so when we add node, we need to assign the node to its father, otherwise the reference will lose outside the function. When we add node, we need to compare its key with its father's key to make sure it's the lchild or rchild of its father. """ if node is None: if new_node.key < father.key: father.lchild = new_node else: father.rchild = new_node new_node.father = father return if new_node.key < node.key: self._insert(node.lchild, node, new_node, 'left') # maintain if node.lchild.priority < node.priority: self.rotate_right(node, father, left_or_right) else: self._insert(node.rchild, node, new_node, 'right') # maintain if node.rchild.priority < node.priority: self.rotate_left(node, father, left_or_right)
前面的邏輯就是BST的插入,也就是和當前節點比大小,決定插入在左邊還是右邊。注意一下,這里我們在插入完成之后,增加了maintain的邏輯,其實也就是比較一下,剛剛進行的插入是否破壞了堆的性質。可能有些同學要問我了,這里為什么只maintain了一次?有可能插入的priority非常小,需要一直旋轉到樹根不是嗎?
的確如此,但是不要忘了,我們這里的maintain邏輯并非只調用一次。隨著整個遞歸的回溯,在樹上的每一層它其實都會執行一次maintain邏輯。所以是可以保證從插入的地方一直維護到樹根的。
查詢
查詢很簡單,不用多說,就是BST的查詢操作,沒有任何變化。
def _query(self, node, key, backup=None): if node is None: return backup if key < node.key: return self._query(node.lchild, key, backup) elif key > node.key: return self._query(node.rchild, key, backup) return node def query(self, key, backup=None): """ Return the result of query a specific node, if not exists return None """ return self._query(self.root, key, backup)
刪除
刪除的操作稍微麻煩了一些,由于涉及到了優先級的維護,不過邏輯也不難理解,只需要牢記需要保證堆的性質即可。
首先,有兩種情況非常簡單,一種是要刪除的節點是葉子節點,這個都很容易想明白,刪除它不會影響任何其他節點,直接刪除即可。第二種情況是鏈節點,也就是說它只有一個孩子,那么刪除它也不會引起變化,只需要將它的孩子過繼給它的父親,整個堆和BST的性質也不會受到影響。
對于這兩種情況之外,我們就沒辦法直接刪除了,因為必然會影響堆的性質。這里有一個很巧妙的做法,就是可以先將要刪除的節點旋轉,將它旋轉成葉子節點或者是鏈節點,再進行刪除。
在這個過程當中,我們需要比較一下它兩個孩子的優先級,確保堆的性質不會受到破壞。
def _delete_node(self, node, father, key, child='left'): """ Implement function of delete node. Defined as a private function that only can be called inside. """ if node is None: return if key < node.key: self._delete_node(node.lchild, node, key) elif key > node.key: self._delete_node(node.rchild, node, key, 'right') else: # 如果是鏈節點,葉子節點的情況也包括了 if node.lchild is None: self.reset_child(father, node.rchild, child) elif node.rchild is None: self.reset_child(father, node.lchild, child) else: # 根據兩個孩子的priority決定是左旋還是右旋 if node.lchild.priority < node.rchild.priority: node = self.rotate_right(node, father, child) self._delete_node(node.rchild, node, key, 'right') else: node = self.rotate_left(node, father, child) self._delete_node(node.lchild, node, key) def delete(self, key): """ Interface of delete method face outside. """ self._delete_node(self.root, None, key, 'left')
修改
修改的操作也非常簡單,我們直接查找到對應的節點,修改它的value即可。
旋轉
我們也貼一下旋轉操作的代碼,其實這里的邏輯和之前SBT當中介紹的旋轉操作是一樣的,代碼也基本相同:
def reset_child(self, node, child, left_or_right='left'): """ Reset the child of father, since in Python all the instances passed by reference, so we need to set the node as a child of its father node. """ if node is None: self.root = child self.root.father = None return if left_or_right == 'left': node.lchild = child else: node.rchild = child if child is not None: child.father = node def rotate_left(self, node, father, left_or_right): """ Left rotate operation of Treap. Example: D / \ A B / \ E C After rotate: B / \ D C / \ A E """ rchild = node.rchild node.rchild = rchild.lchild if rchild.lchild is not None: rchild.lchild.father = node rchild.lchild = node node.father = rchild self.reset_child(father, rchild, left_or_right) return rchild def rotate_right(self, node, father, left_or_right): """ Right rotate operation of Treap. Example: D / \ A B / \ E C After rotate: A / \ E D / \ C B """ lchild = node.lchild node.lchild = lchild.rchild if lchild.rchild is not None: lchild.rchild.father = node lchild.rchild = node node.father = lchild self.reset_child(father, lchild, left_or_right) return lchild
這里唯一要注意的是,由于Python當中存儲的都是引用,所以我們在旋轉操作之后必須要重新覆蓋一下父節點當中當中的值才會生效。負責我們修改了node的引用,但是father當中還是存儲的舊的地址,一樣沒有生效。
關于如何解析平衡二叉搜索樹Treap就分享到這里了,希望以上內容可以對大家有一定的幫助,可以學到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。