Python數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹的實現(xiàn)（下）

weapon 發(fā)布于2019-07-24 18:27 / 3267人閱讀

摘要：現(xiàn)在對我們來說首要的問題是從二叉搜索樹中刪除一個節(jié)點。搜索樹分析通過二叉搜索樹實現(xiàn)的完成，我們將對我們已經(jīng)實現(xiàn)的方法進行一個快速的分析。對它的執(zhí)行效果造成限制的是二叉樹的高度。當(dāng)表示樹的高度時，一個滿二叉樹中節(jié)點的總數(shù)是。

搜索樹實現(xiàn)（續(xù)）

最后，我們把注意力轉(zhuǎn)向二叉搜索樹中最具挑戰(zhàn)性的方法，刪除一個鍵值（參見Listing 7）。首要任務(wù)是要找到搜索樹中要刪除的節(jié)點。如果樹有一個以上的節(jié)點，我們使用_get方法找到需要刪除的節(jié)點。如果樹只有一個節(jié)點，這意味著我們要刪除樹的根，但是我們?nèi)匀灰獧z查根的鍵值是否與要刪除的鍵值匹配。在以上兩種情況下，如果沒有找到該鍵，del操作就會報錯。

Listing 7

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("Error, key not in tree")
   elif self.size == 1 and self.root.key == key:
      self.root = None
      self.size = self.size - 1
   else:
      raise KeyError("Error, key not in tree")

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

一旦我們找到包含要刪除的節(jié)點，我們必須考慮三種情況：

要刪除的節(jié)點沒有孩子(見圖3).

要刪除的節(jié)點只有一個孩子(見圖4).

要刪除的節(jié)點有兩個孩子(見圖5).

第一種情況是最簡單的（參見Listing 8）。如果當(dāng)前節(jié)點沒有孩子，所有我們需要做的是引用刪除該節(jié)點并刪除父節(jié)點的引用。本例的代碼顯示在如下。

Listing 8

if currentNode.isLeaf():
    if currentNode == currentNode.parent.leftChild:
        currentNode.parent.leftChild = None
    else:
        currentNode.parent.rightChild = None

圖 3：刪除鍵值為16的節(jié)點，這個節(jié)點沒有孩子

第二種情況只是稍微復(fù)雜（參見Listing 9）。如果節(jié)點只有一個孩子，那我們可以簡單地讓孩子替換它父母的位置。此案例的代碼如下所示?？吹竭@段代碼，就會發(fā)現(xiàn)有六種情況要考慮。由于是具有左子樹還是右子樹的情況，我們只討論當(dāng)前節(jié)點只有左子樹的情況。具體過程如下：

如果當(dāng)前節(jié)點是左子樹，那我們只需要更新左子樹的引用指向當(dāng)前節(jié)點的父節(jié)點，然后更新父節(jié)點的左子樹引用指向當(dāng)前節(jié)點的左子樹。

如果當(dāng)前節(jié)點是右子樹，那我們只需要更新右子樹的引用指向當(dāng)前節(jié)點的父節(jié)點，然后更新父節(jié)點的右子樹引用指向當(dāng)前節(jié)點的右子樹。

如果當(dāng)前節(jié)點沒有父節(jié)點，它一定是根。這種情況下，我們只需通過調(diào)用replaceNodeData方法把鍵替換為左子樹和右子樹里的數(shù)據(jù)。

Listing 9

else: # this node has one child
   if currentNode.hasLeftChild():
      if currentNode.isLeftChild():
          currentNode.leftChild.parent = currentNode.parent
          currentNode.parent.leftChild = currentNode.leftChild
      elif currentNode.isRightChild():
          currentNode.leftChild.parent = currentNode.parent
          currentNode.parent.rightChild = currentNode.leftChild
      else:
          currentNode.replaceNodeData(currentNode.leftChild.key,
                             currentNode.leftChild.payload,
                             currentNode.leftChild.leftChild,
                             currentNode.leftChild.rightChild)
   else:
      if currentNode.isLeftChild():
          currentNode.rightChild.parent = currentNode.parent
          currentNode.parent.leftChild = currentNode.rightChild
      elif currentNode.isRightChild():
          currentNode.rightChild.parent = currentNode.parent
          currentNode.parent.rightChild = currentNode.rightChild
      else:
          currentNode.replaceNodeData(currentNode.rightChild.key,
                             currentNode.rightChild.payload,
                             currentNode.rightChild.leftChild,
                             currentNode.rightChild.rightChild)

圖 4：刪除鍵值為25的節(jié)點，它是只有一個孩子的節(jié)點

第三種情況是最難處理的情況（參見Listing 10）。如果一個節(jié)點有兩個孩子，我們就不可能簡單地讓其中一個替換節(jié)點的位置，我們需要尋找一個節(jié)點，用來替換這個將要刪除的節(jié)點，我們需要的這個節(jié)點能夠保持現(xiàn)有二叉搜索樹的左、右子樹的關(guān)系。這個節(jié)點在樹中具有第二大的鍵值。我們稱這個節(jié)點為后繼節(jié)點，我們將一路尋找這個后繼節(jié)點，后繼節(jié)點必須保證沒有一個以上的孩子，所以既然我們已經(jīng)知道如何處理這兩種情況，我們就可以實現(xiàn)它了。一旦后繼結(jié)點被刪除，我們把它放在樹中將被刪除的樹節(jié)點處。

圖 5：刪除鍵值為5的節(jié)點，它有兩個孩子節(jié)點

第三種情況的處理代碼如下所示。注意我們是用findSuccessor和findMin方法來輔助找到后繼節(jié)點的。要刪除后繼節(jié)點，我們利用spliceOut方法。我們用spliceOut的原因是它能直接使我們想移除的節(jié)點，做出正確的變化。我們也可以調(diào)用遞歸刪除，但那樣我們就會浪費時間反復(fù)尋找關(guān)鍵節(jié)點。

Listing 10

elif currentNode.hasBothChildren(): #interior
    succ = currentNode.findSuccessor()
    succ.spliceOut()
    currentNode.key = succ.key
    currentNode.payload = succ.payload

找到后繼節(jié)點的代碼如下所示（參見Listing 11），你可以看到TreeNode類的一個方法。這個代碼利用二叉搜索樹中序遍歷的性質(zhì)，從最小到最大打印出樹中的節(jié)點。當(dāng)尋找后繼節(jié)點時需要考慮三種情況：

如果節(jié)點有右子節(jié)點，那么后繼節(jié)點是右子樹中最小的關(guān)鍵節(jié)點。

如果節(jié)點沒有右子節(jié)點，是其父節(jié)點的左子樹，那么父節(jié)點是后繼節(jié)點。

如果節(jié)點是其父節(jié)點的右子節(jié)點，而本身無右子節(jié)點，那么這個節(jié)點的后繼節(jié)點是其父節(jié)點的后繼節(jié)點，但不包括這個節(jié)點。

現(xiàn)在對我們來說首要的問題是從二叉搜索樹中刪除一個節(jié)點。

findMin方法是用來找到子樹中的最小的節(jié)點。你要了解，最小值在任何二叉搜索樹中都是樹最左邊的孩子節(jié)點。因此findMin方法只需要簡單地追蹤左子樹，直到找到?jīng)]有左子樹的葉節(jié)點。

Listing 11

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

我們還需要看看二叉搜索樹的最后一個接口。假設(shè)我們已經(jīng)按順序簡單地遍歷了子樹上所有的鍵值，就肯定是用字典實現(xiàn)的，就會有疑問：為什么不是樹？我們已經(jīng)知道如何使用中序遍歷二叉樹的算法，然而，寫一個迭代器需要更多的操作，因為每次調(diào)用迭代器時，一個迭代器只返回一個節(jié)點。

Python提供了一個創(chuàng)建迭代器的非常強大的功能。這個功能就是yield。yield類似于return，返回一個值給調(diào)用者。然而，yield也需要額外的步驟來暫停函數(shù)的執(zhí)行，以便下次調(diào)用函數(shù)時繼續(xù)執(zhí)行時做準(zhǔn)備。它的功能是創(chuàng)建可迭代的對象，稱為生成器。

二叉樹迭代器的代碼如下所示。仔細(xì)觀察這些代碼：乍一看，你可能會認(rèn)為代碼是非遞歸的。但是請記住，__iter__重寫了for x in的操作符進行迭代，所以它確實是遞歸！因為它是__iter__方法在TreeNode類中定義的TreeNode的實例遞歸。

def __iter__(self):
   if self:
      if self.hasLeftChild():
             for elem in self.leftChiLd:
                yield elem
      yield self.key
      if self.hasRightChild():
             for elem in self.rightChild:
                yield elem

在此，你可能想下載包含BinarySearchTree和TreeNode類完整代碼的文檔。

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

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self


class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    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)

    def __setitem__(self,k,v):
       self.put(k,v)

    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)

    def __contains__(self,key):
       if self._get(key,self.root):
           return True
       else:
           return False

    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("Error, key not in tree")
      elif self.size == 1 and self.root.key == key:
         self.root = None
         self.size = self.size - 1
      else:
         raise KeyError("Error, key not in tree")

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

    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

    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 remove(self,currentNode):
         if currentNode.isLeaf(): #leaf
           if currentNode == currentNode.parent.leftChild:
               currentNode.parent.leftChild = None
           else:
               currentNode.parent.rightChild = None
         elif currentNode.hasBothChildren(): #interior
           succ = currentNode.findSuccessor()
           succ.spliceOut()
           currentNode.key = succ.key
           currentNode.payload = succ.payload

         else: # this node has one child
           if currentNode.hasLeftChild():
             if currentNode.isLeftChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.leftChild
             elif currentNode.isRightChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.leftChild
             else:
                 currentNode.replaceNodeData(currentNode.leftChild.key,
                                    currentNode.leftChild.payload,
                                    currentNode.leftChild.leftChild,
                                    currentNode.leftChild.rightChild)
           else:
             if currentNode.isLeftChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.rightChild
             elif currentNode.isRightChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.rightChild
             else:
                 currentNode.replaceNodeData(currentNode.rightChild.key,
                                    currentNode.rightChild.payload,
                                    currentNode.rightChild.leftChild,
                                    currentNode.rightChild.rightChild)




mytree = BinarySearchTree()
mytree[3]="red"
mytree[4]="blue"
mytree[6]="yellow"
mytree[2]="at"

print(mytree[6])
print(mytree[2])

搜索樹分析

通過二叉搜索樹實現(xiàn)的完成，我們將對我們已經(jīng)實現(xiàn)的方法進行一個快速的分析。讓我們先看一下put這個方法。對它的執(zhí)行效果造成限制的是二叉樹的高度?；叵胍幌抡Z法階段，樹的高度指的是根和最深的葉節(jié)點之間的邊的數(shù)目。高度作為一種限制因素是因為當(dāng)我們在樹中尋找一個合適的位置插入節(jié)點時，我們最多將會對樹的每一級做比較。

二叉樹的高度可能是多少呢？這個問題的答案取決于鍵是怎么被添加到樹中的。如果鍵是以一個隨機的順序加到樹中的，那么當(dāng)節(jié)點的數(shù)目為n時，樹的高度大概是 log₂n。這是因為鍵是隨機地散布的，大約有一半的節(jié)點會比根節(jié)點大，另一半會比它小。記住在二叉樹中，根上有一個節(jié)點，下一級有兩個，再下一級有四個。當(dāng)級數(shù)為d時，這一級的節(jié)點數(shù)目為 2^d。當(dāng)h表示樹的高度時，一個滿二叉樹中節(jié)點的總數(shù)是 2^h+1-1。

一個滿二叉樹中的節(jié)點數(shù)目和一個平衡二叉樹中的左子樹和右子樹的數(shù)目是一樣多的。當(dāng)樹中有n個節(jié)點時put執(zhí)行的最差結(jié)果的時間復(fù)雜度是 O(log₂n)。要注意到這與上一段所說的是逆運算的關(guān)系。所以 log₂n 代表樹的高度，這表示把一個新節(jié)點插入到一個合適位置前，在搜索中需要比較的次數(shù)。

不巧的是，通過插入排序過后的鍵，建造一個高度為n的搜索樹是可能的。圖 6 就展示了這種樹的一個例子，在這種情形下，這時put方法的時間復(fù)雜度為 O(n)。

圖 6：一個傾斜的二叉搜索樹性能會低下

現(xiàn)在你已經(jīng)理解了put方法的效率會受到樹的高度的限制，你可能猜測其他的方法，get，in和del也是受限制的，因為要在樹上尋找鍵，最壞的情形就是一直搜索樹最后卻找不到鍵。乍一看del也許看上去更復(fù)雜，因為它也許需要在刪除操作完成之前一直查找后繼節(jié)點。但是記得，尋找后繼節(jié)點的最壞情形也是取決于樹的高度，這意味著只需要簡單地把工作量加倍，因為加倍是乘以一個常數(shù)因子，所以它不會改變最壞情形的復(fù)雜度。

云服務(wù)器 GPU云服務(wù)器二叉樹的存儲結(jié)構(gòu) 二叉樹的遍歷二叉樹的存儲 java二叉樹的構(gòu)建

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/37756.html

發(fā)表評論

登陸后可評論

0條評論

weapon

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow安裝windows

閱讀 1684·2023-04-26 00:30
（免費領(lǐng)取源碼）基于Springboot+Vue+Element-ui的精美個人博客系統(tǒng)的設(shè)計與實現(xiàn)

閱讀 3156·2021-11-25 09:43
git基本操作

閱讀 2885·2021-11-22 14:56
幾乎影響所有編譯器!“木馬源”漏洞可隱藏在開源代碼中引發(fā)供應(yīng)鏈攻擊

閱讀 3195·2021-11-04 16:15
體驗篇 - 部署IOTA私鏈

閱讀 1156·2021-09-07 09:58
css 3d立方體

閱讀 2029·2019-08-29 13:14
CSS 打印

閱讀 3114·2019-08-29 12:55
使用CSS處理標(biāo)題過長，自動截斷，兼容響應(yīng)式布局

閱讀 993·2019-08-29 10:57

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

Python數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹的實現(xiàn)（下）

相關(guān)文章

*Python**數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹的實現(xiàn)*（上）

*Python**數(shù)據(jù)結(jié)構(gòu)*——AVL樹的基本概念

樹和樹的算法

樹和樹的算法

二叉搜索樹的python實現(xiàn)

發(fā)表評論

0條評論

weapon

男|高級講師

TA的文章

tensorflow安裝windows

（免費領(lǐng)取源碼）基于Springboot+Vue+Element-ui的精美個人博客系統(tǒng)的設(shè)計與實現(xiàn)

git基本操作

幾乎影響所有編譯器!“木馬源”漏洞可隱藏在開源代碼中引發(fā)供應(yīng)鏈攻擊

體驗篇 - 部署IOTA私鏈

css 3d立方體

CSS 打印

使用CSS處理標(biāo)題過長，自動截斷，兼容響應(yīng)式布局

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

Python數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹的實現(xiàn)（下）

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！