python中二元搜尋樹的詳細介紹（程式碼範例）-Python教學-PHP中文網

#**二元搜尋樹(BST binary search tree)**是一種比較特殊的二元樹，表現為任意節點的值都比左孩子的值要大，而且小於等於右孩子的值，採用中序遍歷BST（Binary Search Tree）就可以的到排序好的元素集合，而且插入刪除的時間消耗也比較合理，但是有一個缺點就是記憶體開銷有點大。

二元搜尋樹的性質

1，任意節點x，其左子樹中的key不大於x.key，其右子樹中的key不小於x.key。
2，不同的二元搜尋樹可以代表同一組值的集合。
3，二元搜尋樹的基本操作和樹的高度成正比，所以如果是一棵完全二元樹的話最壞運行時間為Θ(lgn)，但是若是一個n個節點連接成的線性樹，那麼最壞運轉時間是Θ(n)。
4，根節點是唯一一個parent指標指向NIL節點的節點。
5，每一個節點至少包含key、left、right與parent四個屬性，建構二元搜尋樹時，必須存在對key的比較演算法。

二、二元搜尋樹的實作

1. 定義

樹的節點：

class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0

登入後複製

2.插入

現在我們有了BinarySearchTree shell 和TreeNode，現在是時候寫put 方法，這將允許我們建立二元搜尋樹。 put 方法是BinarySearchTree 類別的一個方法。此方法將檢查樹是否已具有根。如果沒有根，那麼 put 將建立一個新的 TreeNode 並將其做為樹的根。如果根節點已經就位，則put 呼叫私有遞歸輔助函數_put 根據下列演算法搜尋樹：

從樹的根開始，搜尋二元樹，將新鍵與目前節點中的鍵進行比較。如果新鍵小於目前節點，則搜尋左子樹。如果新鍵大於目前節點，則搜尋右子樹。
當沒有左（或右）孩子要搜尋時，我們在樹中找到應該建立新節點的位置。
要在樹中新增節點，請建立一個新的 TreeNode對象，並將物件插入到上一個步驟發現的節點。
插入時，總是作為葉節點插入到樹中
給定序列去依次構造二叉查找樹，則二叉搜尋樹唯一；如果是用這個序列所有的關鍵字去構造可能的二元樹（排列任意），則一般不唯一。

def put(self,key,val):
    if self.root:
        self._put(key,val,self.root)
    else:
        self.root = TreeNode(key,val)
    self.size = self.size + 1

def _put(self,key,val,currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftChild():
               self._put(key,val,currentNode.leftChild)
        else:
               currentNode.leftChild = TreeNode(key,val,parent=currentNode)
    else:
        if currentNode.hasRightChild():
               self._put(key,val,currentNode.rightChild)
        else:
               currentNode.rightChild = TreeNode(key,val,parent=currentNode)

登入後複製

上面展示了在樹中插入一個新節點的 Python 程式碼。 _put 函數依照上述步驟遞歸編寫。請注意，當一個新的子節點插入到樹中時，currentNode 將作為父節點傳遞給新的樹節點。
我們實作插入的一個重要問題是重複的鍵不能正確處理。當我們的樹被實現時，重複鍵將在具有原始鍵的節點的右子樹中建立具有相同鍵值的新節點。這樣做的結果是，具有新鍵的節點將永遠不會在搜尋期間被找到。處理插入重複鍵的更好方法是將新鍵相關聯的值取代舊值。

3.找出

一旦樹被構造，下一個任務是實現給定鍵的值的檢索。 get 方法比 put 方法更容易，因為它只是遞歸地搜尋樹，直到它到達不匹配的葉節點或找到匹配的鍵。當找到匹配的鍵時，傳回儲存在節點的有效載荷中的值。

當二元尋找樹不為空時：

首先將給定值與根結點的關鍵字比較，若相等，則尋找成功
若小於根結點的關鍵字值，遞歸查左子樹
#若大於根結點的關鍵字值，遞迴查右子樹
若子樹為空，尋找不成功

def get(self,key):
    if self.root:
        res = self._get(key,self.root)
        if res:
               return res.payload
        else:
               return None
    else:
        return None

def _get(self,key,currentNode):
    if not currentNode:
        return None
    elif currentNode.key == key:
        return currentNode
    elif key < currentNode.key:
        return self._get(key,currentNode.leftChild)
    else:
        return self._get(key,currentNode.rightChild)

def __getitem__(self,key):
    return self.get(key)

登入後複製

4.刪除

第一個任務是透過搜尋樹來找到要刪除的節點。如果樹有多個節點，我們使用 _get 方法搜尋以找到需要刪除的 TreeNode。如果樹只有一個節點，這意味著我們刪除樹的根，但是我們仍然必須檢查以確保根的鍵匹配要刪除的鍵。在任一情況下，如果未找到鍵，del 操作符將引發錯誤。

def delete(self,key):
   if self.size > 1:
      nodeToRemove = self._get(key,self.root)
      if nodeToRemove:
          self.remove(nodeToRemove)
          self.size = self.size-1
      else:
          raise KeyError(&#39;Error, key not in tree&#39;)
   elif self.size == 1 and self.root.key == key:
      self.root = None
      self.size = self.size - 1
   else:
      raise KeyError(&#39;Error, key not in tree&#39;)

def __delitem__(self,key):
    self.delete(key)

登入後複製

一旦我們找到了我們要刪除的鍵的節點，我們必須考慮三種情況：

##要刪除的節點沒有子節點。
要刪除的節點只有一個子節點。
要刪除的節點有兩個子節點。

第一种情况：
如果当前节点没有子节点，我们需要做的是删除节点并删除对父节点中该节点的引用。
第二种情况：
如果一个节点只有一个孩子，那么我们可以简单地促进孩子取代其父。此案例的代码展示在下一个列表中。当你看这个代码，你会看到有六种情况要考虑。由于这些情况相对于左孩子或右孩子对称，我们将仅讨论当前节点具有左孩子的情况。决策如下：

如果当前节点是左子节点，则我们只需要更新左子节点的父引用以指向当前节点的父节点，然后更新父节点的左子节点引用以指向当前节点的左子节点。
如果当前节点是右子节点，则我们只需要更新左子节点的父引用以指向当前节点的父节点，然后更新父节点的右子节点引用以指向当前节点的左子节点。
如果当前节点没有父级，则它是根。在这种情况下，我们将通过在根上调用replaceNodeData 方法来替换 key，payload，leftChild 和 rightChild 数据。
第三种情况：
最难处理的情况。如果一个节点有两个孩子，那么我们不太可能简单地提升其中一个节点来占据节点的位置。然而，我们可以在树中搜索可用于替换被调度删除的节点的节点。我们需要的是一个节点，它将保留现有的左和右子树的二叉搜索树关系。执行此操作的节点是树中具有次最大键的节点。我们将这个节点称为后继节点，我们将看一种方法来很快找到后继节点。继承节点保证没有多于一个孩子，所以我们知道使用已经实现的两种情况删除它。一旦删除了后继，我们只需将它放在树中，代替要删除的节点。
找到后继的代码如下所示，是 TreeNode 类的一个方法。此代码利用二叉搜索树的相同属性，采用中序遍历从最小到最大打印树中的节点。在寻找接班人时，有三种情况需要考虑：
如果节点有右子节点，则后继节点是右子树中的最小的键。
如果节点没有右子节点并且是父节点的左子节点，则父节点是后继节点。
如果节点是其父节点的右子节点，并且它本身没有右子节点，则此节点的后继节点是其父节点的后继节点，不包括此节点。

def findSuccessor(self):
    succ = None
    if self.hasRightChild():
        succ = self.rightChild.findMin()
    else:
        if self.parent:
               if self.isLeftChild():
                   succ = self.parent
               else:
                   self.parent.rightChild = None
                   succ = self.parent.findSuccessor()
                   self.parent.rightChild = self
    return succ

def findMin(self):
    current = self
    while current.hasLeftChild():
        current = current.leftChild
    return current

def spliceOut(self):
    if self.isLeaf():
        if self.isLeftChild():
               self.parent.leftChild = None
        else:
               self.parent.rightChild = None
    elif self.hasAnyChildren():
        if self.hasLeftChild():
               if self.isLeftChild():
                  self.parent.leftChild = self.leftChild
               else:
                  self.parent.rightChild = self.leftChild
               self.leftChild.parent = self.parent
        else:
               if self.isLeftChild():
                  self.parent.leftChild = self.rightChild
               else:
                  self.parent.rightChild = self.rightChild
               self.rightChild.parent = self.parent

登入後複製

三、平衡二叉搜索树（AVL树）

1. 概念

二叉搜索树的深度越小，那么搜索所需要的运算时间越小。一个深度为log(n)的二叉搜索树，搜索算法的时间复杂度也是log(n)。然而，我们在二叉搜索树中已经实现的插入和删除操作并不能让保持log(n)的深度。如果我们按照8，7，6，5，4，3，2，1的顺序插入节点，那么就是一个深度为n的二叉树。那么，搜索算法的时间复杂度为n。
在上一节中我们讨论了建立一个二叉搜索树。我们知道，当树变得不平衡时get和put操作会使二叉搜索树的性能降低到O(n)。
如何减少树的深度呢？
一种想法是先填满一层，再去填充下一层，这样就是一个完全二叉树(complete binary tree)。这样的二叉树实现插入算法会比较复杂。另一种比较容易实现的树状数据结构——AVL树，其搜索算法复杂度为log(n)。
在这一节中我们将看到一种特殊的二叉搜索树，它可以自动进行调整，以确保树随时都保持平衡。这种树被称为AVL树，命名源于其发明者：G.M. Adelson-Velskii 和 E.M. Landis。

AVL樹實作 Map 抽象資料類型就像一個常規的二元搜尋樹，唯一的差異是樹的執行方式。為了實現我們的 AVL樹，我們需要追蹤樹中每個節點的平衡因子。我們透過查看每個節點的左右子樹的高度來做到這一點。更正式地，我們將節點的平衡因子定義為左子樹的高度和右子樹的高度之間的差異。
$#b a l a n c e F a ##c t o r = h e i g h #t (l e f t S u b T r e e) - #- ##h e i g #h t ##(r i g h t S u b T r e e$
#)

使用上面給出的平衡因子的定義，我們說如果平衡因子大於零，則子樹是左重的。如果平衡因子小於零，則子樹是右重的。如果平衡因子是零，那麼樹是完美的平衡。為了實現AVL樹，並且獲得具有平衡樹的好處，如果平衡因子是 -1,0 或 1，我們將定義樹平衡。一旦樹中的節點的平衡因子在這個範圍之外，我們將需要一個程式來使樹恢復平衡。

高度為h的樹的節點數（Nh）為：

Nh=1 Nh−1 Nh−2這個公式和斐波那契序列非常相似。我們可以利用這個公式透過樹中的節點的數目推導出一個AVL樹的高度。隨著斐波那契序列的數字越來越大，Fi / Fi−1 越來越接近黃金比例Φ

在任何時候，我們的AVL樹的高度等於樹中節點數目的對數的常數（1.44）倍。這是搜尋我們的AVL樹的好消息，因為它將搜尋限制為 O(logN)。

python中二元搜尋樹的詳細介紹（程式碼範例） 2.實作

當新增一個節點時，會破壞二元樹的平衡，因此需要透過旋轉來修正。

單一旋轉
執行一個正確的右旋轉，我們需要做到以下幾點：
使左節點成為子樹的根。
######移動舊根到新根的右節點。 ############如果新根原來有右節點，那麼就讓其成為新根右節點的左節點。 ###

註：由於新根是舊根的左節點，移動後的舊根的左節點一定為空。這時可以直接為移動後的舊根添加左節點。
python中二元搜尋樹的詳細介紹（程式碼範例）
同理，執行左旋轉我們需要做到以下幾點：

#讓右邊節點(B)成為子樹的根。
移動舊的根節點(A)到新根的左節點。
如果新根(B)原來有左節點，那麼就讓原來B的左節點成為新根左節點(A)的右節點。

雙旋轉

如圖，如果子節點是4不是2，嘗試單旋轉，會發現無法解決問題。
要解決這個問題，我們必須使用以下規則：

如果子樹需要左旋轉使之平衡，首先檢查右節點的平衡因子。如果右節點左重則右節點右旋轉，然後原節點左旋轉。
如果子樹需要右旋轉使其平衡，首先檢查左節點的平衡因子。如果左節點右重則左節點左旋轉，然後原節點右旋轉。

此時解決方式為雙重旋轉。
python中二元搜尋樹的詳細介紹（程式碼範例）
雙旋轉其實是進行兩次單旋轉: 4為根節點的子樹先進行一次向左的單旋轉，然後將5為根節點的子樹進行了一次向右的單旋轉。這樣恢復了樹的ACL性質。

對於AVL樹，可以證明，在新增一個節點時，總是可以透過一次旋轉來恢復AVL樹的性質。

旋轉規則

當我們插入新的節點時，在哪裡旋轉？是用單旋轉還是雙旋轉?
python中二元搜尋樹的詳細介紹（程式碼範例）
我們按照以下基本步驟進行：

#按照二元搜尋樹的方式增加節點，新增節點稱為一個葉節點。
從新增節點開始，回溯到第一個失衡節點(5)。
(如果回溯到根節點，還沒有失衡節點，就表示該樹已經符合AVL性質。)
找到斷的邊(5->3)，並確定斷弦的方向(5的左側)
以斷邊下端(3)為根節點，確定兩個子樹中的哪一個深度大(左子樹還是右子樹)。
(這兩棵子樹的深度不可能相等，而且深度大的子樹包含有新增節點。)
如果第2和第3步中的方向一致(都為左或都為右)，需要單旋轉以失衡節點為根節點的子樹。
否則，雙旋轉以失衡節點為根節點的子樹。

四、紅黑樹

紅黑樹是一種常用的平衡二元搜尋樹，它是複雜的，但它的操作有著良好的最壞情況運行時間，即操作的複雜度都不會惡化，並且在實踐中是高效的: 它可以在O(logn)時間內做單次的查找，插入和刪除，這裡的n是樹中元素的數目。
紅黑樹是一種很有趣的平衡檢索樹。它的統計表現比平衡二元樹( AVL-樹)，因此，紅黑樹在許多地方都有應用。在C STL中，許多部分(目前包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支援)。
紅黑樹的主要規則：
紅-黑樹的主要規則如下：

節點是紅色或黑色。
根是黑色。
所有葉子都是黑色（葉子是NIL節點）。
每個紅色節點必須有兩個黑色的子節點。 (從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。)
從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。

在紅-黑樹中插入的節點都是紅色的，這不是偶然的，因為插入一個紅色節點比插入一個黑色節點違背紅-黑規則的可能性更小。原因是：插入黑色節點總是會改變黑色高度（違反規則4），但是插入紅色節點只有一半的機會會違反規則3。另外違背規則3比違背規則4要更容易修正。
當插入新的節點時，可能會破壞這種平衡性，紅-黑樹主要透過三種方式對平衡進行修正，改變節點顏色、左旋和右旋。（具體規則省略）
因為每一個紅黑樹也是一個特化的二元查找樹，因此紅黑樹上的唯讀操作與普通二叉查找樹上的唯讀操作相同。然而，在紅黑樹上進行插入操作和刪除操作會導致不再符合紅黑樹的性質。恢復紅黑樹的性質需要少量(O(logn))的顏色變更(實際上是非常快速的)和不超過三次樹旋轉(對於插入操作是兩次)。雖然插入和刪除很複雜，但操作時間仍可保持為O(logn) 次。
一棵有 n 個內部節點的紅黑樹的高度至多為 2lg(n 1).

以上是python中二元搜尋樹的詳細介紹（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！

本網站聲明

本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn