二叉搜索樹
我們已經(jīng)知道了在一個集合中獲取鍵值對的兩種不同的方法。回憶一下這些集合是如何實現(xiàn)ADT（抽象數(shù)據(jù)類型）MAP的。我們討論兩種ADT MAP的實現(xiàn)方式，基于列表的二分查找和哈希表。在這一節(jié)中，我們將要學習二叉搜索樹，這是另一種鍵指向值的Map集合，在這種情況下我們不用考慮元素在樹中的實際位置，但要知道使用二叉樹來搜索更有效率。
搜索樹操作
在我們研究這種實現(xiàn)方式之前，讓我們回顧一下ADT MAP提供的接口。我們會注意到，這種接口和Python的字典非常相似。
- Map() 創(chuàng)建了一個新的空Map集合。
- put(key,val) 在Map中增加了一個新的鍵值對。如果這個鍵已經(jīng)在這個Map中了，那么就用新的值來代替舊的值。
- get(key) 提供一個鍵，返回Map中保存的數(shù)據(jù)，或者返回None。
- del 使用del map[key]這條語句從Map中刪除鍵值對。
- len() 返回Map中保存的鍵值對的數(shù)目
- in 如果所給的鍵在Map中，使用key in map這條語句返回True。
搜索樹實現(xiàn)
一個二叉搜索樹，如果具有左子樹中的鍵值都小于父節(jié)點，而右子樹中的鍵值都大于父節(jié)點的屬性，我們將這種樹稱為BST搜索樹。如之前所述的，當我們實現(xiàn)Map時，BST方法將引導我們實現(xiàn)這一點。圖 1 展示了二叉搜索樹的這一特性，顯示的鍵沒有關聯(lián)任何的值。注意這種屬性適用于每個父節(jié)點和子節(jié)點。所有在左子樹的鍵值都小于根節(jié)點的鍵值，所有右子樹的鍵值都大于根節(jié)點的鍵值。
圖 1：一個簡單的二叉搜索樹
現(xiàn)在你知道什么是二叉搜索樹了，我們再來看如何構造一個二叉搜索樹，我們在搜索樹中按圖 1 顯示的節(jié)點順序插入這些鍵值，圖 1 搜索樹存在的節(jié)點：70,31,93,94,14,23,73。因為 70 是第一個被插入到樹的值，它是根節(jié)點。接下來，31 小于 70，因此是 70 的左子樹。接下來，93 大于 70，因此是 70 的右子樹。我們現(xiàn)在填充了該樹的兩層，所以下一個鍵值，將會是 31 或者 93 的左子樹或右子樹。由于 94 大于 70 和 93，就變成了 93 的右子樹。同樣，14 小于 70 和 31，因此成為了 31 的左子樹。23 也小于 31，因此必須是 31 的左子樹。然而，它大于 14，所以是 14 的右子樹。
為了實現(xiàn)二叉搜索樹，我們將使用節(jié)點和引用的方法，這類似于我們實現(xiàn)鏈表和表達式樹的過程。因為我們必須能夠創(chuàng)建和使用一個空的二叉搜索樹，所以我們將使用兩個類來實現(xiàn)，第一個類我們稱之為 BinarySearchTree，第二個類我們稱之為TreeNode。BinarySearchTree類有一個TreeNode類的引用作為二叉搜索樹的根，在大多數(shù)情況下，外部類定義的外部方法只需檢查樹是否為空，如果在樹上有節(jié)點，要求BinarySearchTree類中含有私有方法把根定義為參數(shù)。在這種情況下，如果樹是空的或者我們想刪除樹的根，我們就必須采用特殊操作。BinarySearchTree類的構造函數(shù)以及一些其他函數(shù)的代碼如Listing 1 所示。
Listing 1
class BinarySearchTree: def __init__(self): self.root = None self.size = 0 def length(self): return self.size def __len__(self): return self.size def __iter__(self): return self.root.__iter__()
TreeNode類提供了許多輔助函數(shù)，使得BinarySearchTree類的方法更容易實現(xiàn)過程。如Listing 2 所示，一個樹節(jié)點的結構，是由這些輔助函數(shù)實現(xiàn)的。正如你看到的那樣，這些輔助函數(shù)可以根據(jù)自己的位置來劃分一個節(jié)點作為左或右孩子和該子節(jié)點的類型。TreeNode類非常清楚地跟蹤了每個父節(jié)點的屬性。當我們討論刪除操作的實現(xiàn)時，你將明白為什么這很重要。
對于Listing 2 中的TreeNode實現(xiàn)，另一個有趣的地方是，我們使用Python的可選參數(shù)。可選的參數(shù)很容易讓我們在幾種不同的情況下創(chuàng)建一個樹節(jié)點，有時我們想創(chuàng)建一個新的樹節(jié)點，即使我們已經(jīng)有了父節(jié)點和子節(jié)點。與現(xiàn)有的父節(jié)點和子節(jié)點一樣，我們可以通過父節(jié)點和子節(jié)點作為參數(shù)。有時我們也會創(chuàng)建一個包含鍵值對的樹，我們不會傳遞父節(jié)點或子節(jié)點的任何參數(shù)。在這種情況下，我們將使用可選參數(shù)的默認值。
Listing 2
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
現(xiàn)在，我們擁有了BinarySearchTree和TreeNode類，是時候?qū)懸粋€put方法使我們能夠建立二叉搜索樹。put方法是BinarySearchTree類的一個方法。這個方法將檢查這棵樹是否已經(jīng)有根。如果沒有，我們將創(chuàng)建一個新的樹節(jié)點并把它設置為樹的根。如果已經(jīng)有一個根節(jié)點，我們就調(diào)用它自己，進行遞歸，用輔助函數(shù)_put按下列算法來搜索樹：
從樹的根節(jié)點開始，通過搜索二叉樹來比較新的鍵值和當前節(jié)點的鍵值，如果新的鍵值小于當前節(jié)點，則搜索左子樹。如果新的關鍵大于當前節(jié)點，則搜索右子樹。
當搜索不到左（或右）子樹，我們在樹中所處的位置就是設置新節(jié)點的位置。
向樹中添加一個節(jié)點，創(chuàng)建一個新的TreeNode對象并在這個點的上一個節(jié)點中插入這個對象。
Listing 3 顯示了在樹中插入新節(jié)點的Python代碼。_put函數(shù)要按照上述的步驟編寫遞歸算法。注意，當一個新的子樹插入時，當前節(jié)點（CurrentNode）作為父節(jié)點傳遞給新的樹。
我們執(zhí)行插入的一個重要問題是重復的鍵值不能被正確的處理，我們的樹實現(xiàn)了鍵值的復制，它將在右子樹創(chuàng)建一個與原來節(jié)點鍵值相同的新節(jié)點。這樣做的后果是，新的節(jié)點將不會在搜索過程中被發(fā)現(xiàn)。我們用一個更好的方式來處理插入重復的鍵值，舊的值被新鍵關聯(lián)的值替換。我們把這個錯誤的修復，作為練習留給你。
Listing 3
def put(self,key,val): if self.root: self._put(key,val,self.root) else: self.root = TreeNode(key,val) self.size = self.size + 1def _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)
隨著put方法的實現(xiàn)，我們可以很容易地通過__setitem__方法重載[]作為操作符來調(diào)用put方法（參見Listing 4）。這使我們能夠編寫像myZipTree['Plymouth'] = 55446一樣的python語句，這看上去就像Python的字典。
Listing 4
def __setitem__(self,k,v): self.put(k,v)
圖 2 說明了將新節(jié)點插入到一個二叉搜索樹的過程?；疑?jié)點顯示了插入過程中遍歷樹節(jié)點順序。
圖 2: 插入一個鍵值 = 19 的節(jié)點
一旦樹被構造，接下來的任務就是為一個給定的鍵值實現(xiàn)檢索。get方法比put方法更容易因為它只需遞歸搜索樹，直到發(fā)現(xiàn)不匹配的葉節(jié)點或找到一個匹配的鍵值。當找到一個匹配的鍵值后，就會返回節(jié)點中的值。
Listing 5 顯示了get，_get和__getitem__的代碼。用_get方法搜索的代碼與put方法具有相同的選擇左或右子樹的邏輯。請注意，_get方法返回TreeNode中get的值，_get就可以作為一個靈活有效的方式，為BinarySearchTree的其他可能需要使用TreeNode里的數(shù)據(jù)的方法提供參數(shù)。
通過實現(xiàn)__getitem__方法，我們可以寫一個看起來就像我們訪問字典一樣的Python語句，而事實上我們只是操作二叉搜索樹，例如Z = myziptree ['fargo']。正如你所看到的，__getitem__方法都是在調(diào)用get。
Listing 5
def get(self,key): if self.root: res = self._get(key,self.root) if res: return res.payload else: return None else: return Nonedef _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)
使用get，我們可以通過寫一個BinarySearchTree的__contains__方法來實現(xiàn)操作，__contains__方法簡單地調(diào)用了get方法，如果它有返回值就返回True，如果它是None就返回False。如Listing 6 所示。
Listing 6
def __contains__(self,key): if self._get(key,self.root): return True else: return False
回顧一下__contains__重載的操作符，這允許我們寫這樣的語句：
if 'Northfield' in myZipTree: print("oom ya ya") 
