Notes on Implementing Data Structures and Algorithms with Python（二）

03-02

Notes on Implementing Data Structures and Algorithms with Python

筆記的內容形式：簡要介紹以及代碼實現，分三部分（有交叉）：

第一部分是數據結構和與它們相關的常見問題。內容順序：線性結構（棧，堆，鏈表）、樹、圖（遍歷和最短路徑）。

第二部分是一些重要思想和演算法。內容順序：遞歸、分治、貪心、動態規劃、查找、排序。

第三部分是刷題筆記。

主要參考資料：

https://interactivepython.org/courselib/static/pythonds/index.html

http://javayhu.me/python/

Python Algorithms: Mastering Basic Algorithms in the Python Language by Magnus Lie Hetland.

筆記原先是寫在jupyter notebook，導出md格式後在知乎導入。全部更完之後附上ipynb文件，文章增加目錄索引，食用效果更佳。

計劃：（一）線性數據結構；（二）樹數據機構；（三）圖數據結構；（四）演算法設計；（五）查找和排序；（六）其他演算法和刷題；

本篇為筆記的第（二）篇，對二叉樹，二叉搜索樹，平衡二叉搜索樹的筆記。

樹型數據結構，依次學習二叉堆、二叉搜索樹、平衡二叉搜索樹。

二叉樹的數據結構

其中insert操作是把傳入的node作為父節點，為它增加/修改左右節點。

# 二叉樹class BinaryTree: def __init__(self, root): self.key = root self.left = None self.right = None def insert_left(self, node): if self.left is None: self.left = node else: node = BinaryTree(node) node.left = self.left self.left = node def insert_right(self, node): if self.right is None: self.right = node else: node = BinaryTree(node) node.right = self.right self.right = node def get_left(self): return self.left def get_right(self): return self.right def set_val(self, obj): self.key = obj def get_val(self): return self.key

對於有序的樹（如下面要介紹的二叉排序樹），由於一開始我們對於一棵樹只掌握了它的根節點，而且二叉樹可以看作鏈表（一叉樹）的拓展，所以插入新節點和刪除已有節點的操作和鏈表的操作過程是類似的，即需要執行遍歷樹的操作，有前序、中序、後序遍歷三種方式，分別有迭代版本和遞歸版本共六種實現。

遞歸版的樹遍歷可以寫作一個額外的函數，也可以作為一個方法放在上面實現的BinaryTree類裡面；前者可能比較好，因為我們往往不是單純的遍歷一棵樹，而是要在遍歷時做點操作，比如增刪節點。

# pre, in, post traversal by Rec.def preOrder(tree): if tree: print(tree.get_val()) preOrder(tree.get_left()) preOrder(tree.get_right())def inOrder(tree): if tree: inOrder(tree.get_left()) print(tree.get_val()) inOrder(tree.get_right())def postOrder(tree): if tree: postOrder(tree.get_left()) postOrder(tree.get_right()) print(tree.get_val())# pre, in, post traversal by Iter.# Later...

對於一顆這樣的表示數學表達式的解析樹（Parse Tree）,它的計算過程類似後序遍歷，而把表達式列印出來又非常類似中序遍歷。

# evaluate the math expr.def postordereval(tree): opers = {+:operator.add, -:operator.sub, *:operator.mul, /:operator.truediv} res1 = None res2 = None if tree: res1 = postordereval(tree.getLeftChild()) res2 = postordereval(tree.getRightChild()) if res1 and res2: return opers[tree.getRootVal()](res1,res2) else: return tree.getRootVal()# print the expr with parentheses.def printexp(tree): sVal = "" if tree: sVal = ( + printexp(tree.getLeftChild()) sVal = sVal + str(tree.getRootVal()) sVal = sVal + printexp(tree.getRightChild())+) return sVal

優先隊列，最小堆：

隊列中項目的邏輯順序由其優先順序（用數值的大小來確定）確定。優先順序最高的項目位於隊列的前面，最低優先順序的項目位於後面。在一些圖演算法中應用廣泛。如果用有序鏈表和排序演算法來實現優先隊列，則插入是O(n),排序是O(nlogn)，更好的選擇是使用二叉堆來實現，這樣入隊和出隊操作都是O(logn)。

二叉堆分為最大推（最大值排在最前面）/最小堆，同時是完全二叉樹（不一定滿）。最小堆存儲的序列通過樹的層次遍歷可以畫出完全二叉樹，如下圖：

這裡用python的list來構建最小堆，注意一開始就存在初始元素0，不去用它，但能簡化後面整數除法的操作，並且最後一個元素的索引和current_size相同。

插入操作：append到items列表（保證了完全樹的性質）；判斷新節點的值是不是比它的parent小，如果是，交換它們（保證了堆的性質）。

為了實現插入（insert）時的節點上移，設計了percup函數：需要獲取新節點的parent節點，把新節點的索引整除以2即得到其parent的索引；由於可能需要比較、調整多次父、子節點，至多移動到堆頂，用while遍歷直到堆頂；

然後是刪除最小節點（delMin）或者說出隊（deque），最小元素已經在堆頂，難點是刪除之後的恢復結構，分兩步：

step1：刪除最小元素，把堆的最後一個元素移動到最小元素的位置以維護堆的結構；
step2：把新的根節點下移到合適的位置：和子節點比較，如果比它大，交換。注意這裡需要比兩個子節點都小！所以設計了minchild方法來獲取較小的那個子節點。通過節點索引乘2、乘2加1即獲得兩個子節點的索引。

perc_down函數是實現節點的下移。

最後，實現對輸入的一個序列建堆：對於輸入的整個序列原地修改，從最後一個非葉子節點（len(inputlist) // 2）開始直到根節點（while i > 0）執行節點的下移（percdown）操作。可以這樣理解，因為根節點是最後才調整的，所以才能利用下面已經排好的節點選出最小元素。

這樣的建堆方法的時間複雜度只有O(n)，要優於從序列中一個個取出元素，然後二分搜索（O(logn)）尋找合適的位置進行插入（O(n)）的時間複雜度O(nlogn)。基於O(n)的建堆方法，可以實現O(nlogn)的堆排序演算法。

# 堆二叉堆是完全二叉樹class BinHeap: def __init__(self): self.items = [0] self.current_size = 0 def perc_up(self, i): # 接受參數i是待移動元素的索引 while i // 2 > 0: if self.items[i] < self.items[i//2]: tmp = self.items[i//2] # can not write as a,b = b,a self.items[i//2] = self.items[i] self.items[i] = tmp i = i // 2 def insert(self, value): self.items.append(value) self.current_size = self.current_size + 1 self.perc_up(self.current_size) def perc_down(self, i): # 接受參數i是待移動元素的索引 while 2 * i <= self.current_size: min_child = self.min_child(i) if self.items[i] > self.items[min_child]: tmp = self.items[min_child] self.items[min_child] = self.items[i] self.items[i] = tmp i = min_child def min_child(self, i): # 獲取當前節點的兩個孩子中較小的那個的索引 if 2 * i + 1 > self.current_size: # in case no right child return 2 * i else: if self.items[2*i+1] < self.items[2*i]: return 2*i+1 else: return 2*i def del_min(self): del_val = self.items[1] # heap top, min one. self.items[1] = self.items[self.current_size] self.items.pop() self.current_size = self.current_size - 1 self.perc_down(1) return del_val def build_heap(self, a_list): # 建堆必須從[最後一個非葉子節點]到[第一個非葉子節點]遍歷進行操作： # 應該是：建最大堆：perc_up # 建最小堆： perc_down self.current_size = len(a_list) i = len(a_list) // 2 # [最後一個非葉子節點] self.items = self.items + a_list[:] while i > 0: # 等於0說明到了根節點 self.perc_down(i) i -= 1 bh = BinHeap()bh.build_heap([9,5,6,2,3])print(bh.del_min())print(bh.del_min())print(bh.del_min())print(bh.del_min())print(bh.del_min())23569

堆排序。首先建立最小堆，然後從後往前遍歷它，由於第一個元素為最小值，把它與當前無序區的最後一個元素（i）交換，並重新調整堆使得保持最小堆結構。

def heapSort(alist): bh = BinHeap() length = len(alist) bh.build_heap(alist) for i in range(length, 0, -1): bh.items[1], bh.items[i] = bh.items[i], bh.items[1] bh.perc_down(1) return bh.itemsL = [49,38,65,97,76,13,67,47]L = heapSort(L)del(L[0])print(L)[13, 47, 38, 67, 76, 49, 65, 97]

接下來記錄二叉搜索樹，或稱查找樹，或稱排序樹，都是一個東西。

二叉搜索樹（BST）的任一節點的key值（BST是一種key-value pair容器，這樣的容器也稱為map；其他的map有比如list，hash table（筆記在搜索部分））比左子樹的key值大，比右邊的小。

為了能夠創建並使用一個空的二叉搜索樹，實現將使用兩個類：TreeNode, BinSearchTree。後者的根節點是前者的引用。

# 二叉查找/搜索（search）樹，也叫二叉排序（sort）樹class TreeNode: def __init__(self, key, val, left=None, right=None, parent=None, bf=0): self.key = key self.value = val self.leftChild = left self.rightChild = right self.parent = parent # keep track of parent, useful in BSTs del method. self.balanceFactor = bf # for AVL Tree. # some helper function...help to classify a node...by nodes pos and kind. 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.leftChild or self.rightChild) def hasAnyChild(self): return self.leftChild or self.rightChild def hasBothChild(self): return self.leftChild and self.rightChild def replaceNodeData(self, key, val, lc, rc): self.key = key self.val = val self.leftChild = lc self.rightChild = rc if self.hasLeftChild(): self.leftChild.parent = self if self.hasRightChild(): self.rightChild.parent = self 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

BST的插入（insert）key-value對的操作：

首先檢查樹是否已有root: 沒有的話，創建新節點, 作為root；

已有root的話：

step1: 從root開始，搜索二叉樹。如果新key值小於當前的節點，繼續搜索左子樹；若大於則搜索右子樹；當沒有子樹可以搜索時，即找到合適的插入位置；注意，如果樹中已存在相同的Key值，則把已有節點的val值更新為新的val；

step2: 使用key-value創建新節點，在找到的位置插入節點；

插入節點的圖示：灰色的是搜索過程中訪問到的節點，黑色的是最後確定的位置。

BST的get操作根據key值返回節點的value值，實現方法是上面的insert的一個子操作。

BST的delete操作：

step1: 檢查樹的節點個數，如果只有一個節點（root），如果key值匹配，刪除root重置None，size-1，不匹配則輸入有誤；如果有多個節點，轉step2:

step2: 根據key值，搜索到要被刪除的節點；

step3: 刪除，分三種情況：

1.待刪除節點沒有左右孩子，刪除其父節點對它的連接；

2.節點只有一個孩子（左或右），用其孩子（左或右）代替它與其父節點連接；根據其孩子是左還是右，其本身是父節點的左還是右或者其本身是root分兩種情況去處理；

3.節點同時有左右孩子，先找到其後繼(successor，最接近它的比它大的那個節點)，然後移走後繼，再用後繼代替待刪除節點。

其中找到節點A的後繼的方法：

先判斷節點A是否有右子樹，如果有，再查找關鍵字最小的節點；如果沒有，則從節點A的父節點開始向上查找，直到遇到某個節點是其父節點的左兒子為止，則該父節點為後繼。當然，如果只是為了解決第3中情況的刪除節點，節點A當然是有右子樹的。

不要忘記刪除節點後size-1。下面三張圖分別是1.2.3三種情況。

最後，實現特殊方法__iter__, 能夠用for..in..的方式取出BST的元素，注意到用中序遍歷的方法即可實現。

class BinSearchTree: def __init__(self): self.root = None self.size = 0 def size(self): return self.size def __len__(self): return self.size def __iter__(self): return self.root.__iter__() def insert(self, key, val): if self.root: self._insert(key, val, self.root) # call the private function else: self.root = TreeNode(key, val) def _insert(self, key, val, currentNode): # recursion. if key < currentNode.key: if currentNode.hasLeftChild(): self._insert(key, val, currentNode.leftChild) else: currentNode.leftChild = TreeNode(key, val, parent=currentNode) # when insert, currentNode is its parent. self.size += 1 elif key > currentNode.key: if currentNode.hasRightChild(): self._insert(key, val, currentNode.rightChild) else: currentNode.rightChild = TreeNode(key, val, parent=currentNode) self.size += 1 else: currentNode.val = val def __setitem__(self, key, value): self.insert(key, value) def get(self, key): if self.root: getnode = self._get(key, self.root) if getnode: return getnode.value else: return None else: return None def _get(self, key, currentNode): if not currentNode: return None elif currentNode.key == key: return currentNode elif currentNode.key > 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 return False def delete(self, key): if self.size == 1 and key == self.root.key: self.root = None self.size -= 1 elif self.size > 1: todel = self._get(key, self.root) if todel: self._delete(todel) self.size -= 1 else: raise KeyError("key not in tree.") else: raise KeyError("ket not in tree.") def _delete(self, deleteNode): if deleteNode.isLeaf(): # case 1 if deleteNode.isLeftChild(): deleteNode.parent.leftChild = None else: deleteNode.parent.rightChild = None elif deleteNode.hasBothChild(): # case 3 succ = self.findSuccessor(deleteNode) self._delete(succ) # remove the successor by resursion for simplicity, would waste time for re-searching thought. deleteNode.key = succ.key deleteNode.val = succ.value else: # case 2 if deleteNode.hasLeftChild(): if deleteNode.isLeftChild(): deleteNode.parent.leftChild = deleteNode.leftChild deleteNode.leftChild.parent = deleteNode.parent elif deleteNode.isRightChild(): deleteNode.parent.rightChild = deleteNode.leftChild deleteNode.rightChild.parent = deleteNode.parent else: # it is the root deleteNode.replaceNodeData(deleteNode.leftChild.key, deleteNode.leftChild.value, deleteNode.leftChild.leftChild, deleteNode.leftChild.rightChild) else: if deleteNode.isLeftChild(): deleteNode.rightChild.parent = deleteNode.parent deleteNode.parent.leftChild = deleteNode.rightChild elif deleteNode.isRightChild(): deleteNode.parent.rightChild = deleteNode.rightChild deleteNode.rightChild.parent = deleteNode.parent else: deleteNode.replaceNodeData(deleteNode.rightChild.key, deleteNode.rightChild.value, deleteNode.rightChild.leftChild, deleteNode.rightChild.rightChild) def findSuccessor(self, currentNode): succ = None if currentNode.hasRightChild(): # search the min one in right sub-tree current = currentNode while current.hasLeftChild(): current = current.leftChild succ = current else: # search up from its father until a leftchild node if currentNode.parent: if currentNode.isLeftChild(): currentNode = currentNode.parent else: if currentNode.isLeftChild(): succ = currentNode.parent else: currentNode.parent.rightChild = None # careful. otherwise find succ is current self succ = currentNode.parent.findSuccessor() currentNode.parent.rightChild = currentNode # reconnect it return succ def __delitem__(self, key): self.delete(key)# testmytree = BinSearchTree()mytree[3]="red"mytree[4]="blue"mytree[6]="yellow"mytree[2]="at"print(mytree[6])print(mytree[2])print(mytree.root.key)print(list(i for i in mytree))del mytree[3]print(mytree.root.key)print(list(i for i in mytree))mytree[1] = pinkprint(list(i for i in mytree))del mytree[4]print(list(i for i in mytree))yellowat3[2, 3, 4, 6]2[2, 4, 6][1, 2, 4, 6][1, 2, 6]

具有n個節點的BST的高度在logn到n之間，前者是平衡二叉搜索樹的情況。在平衡樹中，put操作的最壞情況是O(logn)，logn即最多需要比較的次數。

如果輸入的序列是有序（[10,20,30,40,50]）的，按順序插入構造BST時，樹的形狀就退化成線性的：

get,in和del操作也是類似，性能受到樹高度的影響。最壞O(n),平衡時最好，節點的查找，插入，刪除的時間複雜度都是O(logn)。

平衡二叉搜索樹的一種，AVL樹

相比上面的BST樹，只是增加了調整樹結構的操作，由此引入平衡因子和旋轉操作。

平衡因子（BF）：balanceFactor = height(leftSubTree) - height(rightSubTree) 值為-1,0,1時稱樹是平衡的。

每次增加一個節點時，需要修改節點的parent（如果有的話）的平衡因子。如果調整後其parent的BF是0，當然不用進一步操作了；但是注意如果不為0，需要繼續往上遞歸的調整parent的parent的BF值。

此外，如果增加節點後BF絕對值≥2，需要重新旋轉樹的結構使之平衡。

子樹的左旋：右邊重時。根的右孩子成為新的根，原來的根成為新根的左孩子；如果新的根原來有左孩子，則再讓這個左孩子成為原來的根（現在的根的左孩子）的右孩子。

子樹的右旋：左邊重時。根的左孩子成為新的根，原來的根成為新根的右孩子；如果新的根原來有右孩子，則再讓這個右孩子成為原來的根（現在的根的右孩子）的左孩子；

子樹的左右旋和右左旋：單一的左旋和右旋都不能調整成功時。當子樹需要左旋時，先檢查右孩子的BF值，如果BF是＞0的（左重的），則在左旋之前做一次對這個右孩子的右旋。反過來，當子樹需要右旋時，先檢查左孩子的BF，如果左孩子右重，則在右旋之前做一次對這個左孩子的左旋。

注意，旋轉後還需要修改新根和原來的根的BF值，其他節點的BF不受影響。

刪除操作按下不表。

class AVLTree(BinSearchTree): # 繼承BST # 需要修改BST的_insert函數，在插入節點後調用updateBalance(currentNode.leftChild)函數 def _insert(self,key,val,currentNode): if key < currentNode.key: if currentNode.hasLeftChild(): self._insert(key,val,currentNode.leftChild) else: currentNode.leftChild = TreeNode(key,val,parent=currentNode) self.updateBalance(currentNode.leftChild) else: if currentNode.hasRightChild(): self._insert(key,val,currentNode.rightChild) else: currentNode.rightChild = TreeNode(key,val,parent=currentNode) self.updateBalance(currentNode.rightChild) def updateBalance(self, node): if node.balanceFactor > 1 or node.balanceFactor < -1: self.rebalance(node) else: if node.parent: if node.isLeftChild(): node.parent.balanceFactor += 1 elif node.isRightChild(): node.parent.balanceFactor -= 1 if node.parent.balanceFactor != 0: self.updateBalance(node.parent) # 用一個臨時變數newRoot來跟蹤子樹的新根. remember 4 steps: connect child, connect parent, connect themselves, update BF. def rotateLeft(self, rotRoot): newRoot = rotRoot.rightChild rotRoot.rightChild = newRoot.leftChild # necessary, otherwise ori root would still think new root as child. if newRoot.leftChild is not None: newRoot.leftChild.parent = rotRoot newRoot.parent = rotRoot.parent # new root success the oris parent if rotRoot.isRoot(): self.root = newRoot else: if rotRoot.isLeftChild(): rotRoot.parent.leftChild = newRoot else: rotRoot.parent.rightChild = newRoot newRoot.leftChild = rotRoot rotRoot.parent = newRoot rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(newRoot.balanceFactor, 0) # skip the derivation for now. newRoot.balanceFactor = newRoot.balanceFactor + 1 - max(rotRoot.balanceFactor, 0) def rotateRight(self, rotRoot): # symmetrical to rotateLeft. newRoot = rotRoot.leftChild rotRoot.leftChild = newRoot.rightChild # deal child if newRoot.rightChild != None: newRoot.rightChild.parent = rotRoot #deal child parent newRoot.parent = rotRoot.parent #deal root parent if rotRoot.isRoot(): self.root = newRoot else: if rotRoot.isLeftChild(): rotRoot.parent.leftChild = newRoot else: rotRoot.parent.rightChild = newRoot newRoot.rightChild = rotRoot rotRoot.parent = newRoot rotRoot.balanceFactor = rotRoot.balanceFactor - 1 - min(newRoot.balanceFactor, 0) newRoot.balanceFactor = newRoot.balanceFactor - 1 + max(rotRoot.balanceFactor, 0) def rebalance(self, node): if node.balanceFactor < 0: if node.rightChild.balanceFactor > 0: self.rotateRight(node.rightChild) self.rotateLeft(node) elif node.balanceFactor > 0: if node.leftChild.balanceFactor < 0: self.rotateLeft(node.leftChild) self.rotateRight(node)# test avl treemyavltree = AVLTree()myavltree[3]="red"myavltree[4]="blue"myavltree[6]="yellow"myavltree[2]="at"#myavltree[5]=dog#myavltree[1]=catprint(myavltree.root.balanceFactor)print(myavltree.root.value)print(myavltree.root.leftChild.value)print(myavltree.root.rightChild.value)print(list(i for i in myavltree))1blueredyellow[2, 3, 4, 6]

MAP ADT的性能比較：

Summary：we have looked at algorithms that use trees to do the following:

A binary tree for parsing and evaluating expressions.
A binary search tree for implementing the map ADT.
A balanced binary tree (AVL tree) for implementing the map ADT.
A binary tree to implement a min heap.
A min heap used to implement a priority queue.