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

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

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

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

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

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ǎng)h除的節(jié)點(diǎn)，我們必須考慮三種情況：

要?jiǎng)h除的節(jié)點(diǎn)沒有孩子(見圖3).

要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)孩子(見圖4).

要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)孩子(見圖5).

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

Listing 8

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

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

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

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

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

如果當(dāng)前節(jié)點(diǎn)沒有父節(jié)點(diǎn)，它一定是根。這種情況下，我們只需通過調(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é)點(diǎn)，它是只有一個(gè)孩子的節(jié)點(diǎn)

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

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

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

Listing 10

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

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

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

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

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

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

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

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

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

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

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

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])

搜索樹分析

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

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

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

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

圖 6：一個(gè)傾斜的二叉搜索樹性能會(huì)低下

現(xiàn)在你已經(jīng)理解了put方法的效率會(huì)受到樹的高度的限制，你可能猜測其他的方法，get，in和del也是受限制的，因?yàn)橐跇渖蠈ふ益I，最壞的情形就是一直搜索樹最后卻找不到鍵。乍一看del也許看上去更復(fù)雜，因?yàn)樗苍S需要在刪除操作完成之前一直查找后繼節(jié)點(diǎn)。但是記得，尋找后繼節(jié)點(diǎn)的最壞情形也是取決于樹的高度，這意味著只需要簡單地把工作量加倍，因?yàn)榧颖妒浅艘砸粋€(gè)常數(shù)因子，所以它不會(huì)改變最壞情形的復(fù)雜度。

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

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

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

發(fā)表評論

登陸后可評論

0條評論

weapon

男|高級(jí)講師

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

TA的文章

tensorflow安裝windows

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

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

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

閱讀 3186·2021-11-04 16:15
體驗(yàn)篇 - 部署IOTA私鏈

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

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

閱讀 3109·2019-08-29 12:55
使用CSS處理標(biāo)題過長，自動(dòng)截?cái)?，兼容響?yīng)式布局

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

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

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

相關(guān)文章

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

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

樹和樹的算法

樹和樹的算法

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

發(fā)表評論

0條評論

weapon

男|高級(jí)講師

TA的文章

tensorflow安裝windows

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

git基本操作

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

體驗(yàn)篇 - 部署IOTA私鏈

css 3d立方體

CSS 打印

使用CSS處理標(biāo)題過長，自動(dòng)截?cái)?，兼容響?yīng)式布局

最新活動(dòng)

資訊專欄INFORMATION COLUMN

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

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

相關(guān)文章

發(fā)表評論

0條評論

男|高級(jí)講師

TA的文章

最新活動(dòng)

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