合縱連橫: 從定義出發，理解 二元搜尋樹 背後的本質

said alamri on Unsplash

這篇文章，會帶著大家複習以前學過的二元搜尋樹(Binary Search Tree)框架，

並且以二分搜尋樹的概念與定義為核心，

貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。

二元搜尋樹(Binary Search Tree)的定義

左子樹的節點值一定都比根結點值還小。

右子樹的節點值一定都比根結點值還大。

所有子樹都遵循相同的遞回定義。

不論是新增節點、刪除節點、還是查詢節點，都必須滿足這個定義。

整個二元搜尋樹BST的結構可以用下方這個示意圖表示:

接下來，我們會用這個上面這種結構，貫穿一些同類型，有關聯的題目

(請讀者、或觀眾留意上面的這種 二元搜尋樹 框架，之後的解說會反覆出現)

Search in a Binary Search Tree

在一個已知的二元搜尋樹，搜尋某個目標值。

依照定義出發即可，寫起來很像二元樹版本的Binary Search。

迭代版本的程式碼

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        
        cur = root
        
        while cur is not None:
            
            if cur.val == val:
                #  hit
                return cur
            
            elif cur.val > val:
									# val is smaller than current node value, serach left sub-tree
                cur = cur.left
                
            else:
									# val is larger than current node value, serach right sub-tree
                cur = cur.right
        
        # miss
        return None

遞回版本的程式碼

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        
        if not root:
            return None

        if val < root.val:
            # val is smaller then root.val, search left subtree
            return self.searchBST(root.left, val)

        elif val > root.val:
            # val is larger than root.val, search right subtree
            return self.searchBST(root.right, val)
            
        else:
            # val is equal to root.val, this is answer
            return root

Insert into a Binary Search Tree

在一個已知的二元搜尋樹，搜尋一個節點，帶有指定的值val。

和搜尋其實很像，也是利用二元搜尋樹已經排序的特性，來根據定義來尋找插入位置，接著放入新增的節點。

迭代版本的程式碼

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root: return TreeNode(val)
            
        cur, next = None, root
        while next:
            cur = next
            next = cur.left if val < cur.val else cur.right
        
        if val < cur.val: 
            cur.left = TreeNode(val)
        else: 
            cur.right = TreeNode(val)
            
        return root

遞回版本的程式碼

class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        
        ## Base case
        # Already found insertion place
        if not root:
            node = TreeNode( val )
            return node
            
            
        ## General cases
        # Insert with BST ordering rule
        
        if val > root.val:
            root.right = self.insertIntoBST(root.right, val)

        else:
            root.left = self.insertIntoBST(root.left, val)

        return root

查詢、新增都複習了，接下來就是刪除節點。

Delete Node in a BST

前面提過，不論作哪一種操作，都要保持BST左邊小，右邊大的已排序性質。

那刪除之後，要找誰遞補這個空缺呢?

有兩個解，兩組都可以。

第一種: 選擇被刪除的節點的左子樹裡面的最大節點值。

第二種: 選擇被刪除的節點的右子樹裡面的最小節點值。

第一種解: 選擇被刪除的節點的左子樹裡面的最大節點值。

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        
        if not root:
            return None
            
        if root.val > key:
		    # Target node is smaller than currnet node, search left subtree
			
			       root.left = self.deleteNode( root.left, key )

        elif root.val < key:
		    # Target node is larger than currnet node, search right subtree
			
			       root.right = self.deleteNode( root.right, key )

        else:
            # Current node is target node
			
			       if (not root.left) or (not root.right):
            		# At least one child is empty
            		# Target node is replaced by either non-empty child or None
            		root = root.left if root.left else root.right

            else:
                # Both two childs exist
                # Target node is replaced by largest element of left subtree
                cur = root.left

                while cur.right:
                    cur = cur.right

                root.val = cur.val
                root.left = self.deleteNode( root.left, cur.val )
                    
        return root

​第二種解: 選擇被刪除的節點的右子樹裡面的最小節點值。

class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        
        if not root:
            return None
            
        if root.val > key:
		    		# Target node is smaller than currnet node, search left subtree
			
           	root.left = self.deleteNode( root.left, key )

        elif root.val < key:
		    # Target node is larger than currnet node, search right subtree
			
            root.right = self.deleteNode( root.right, key )

        else:
            # Current node is target node
			
            if (not root.left) or (not root.right):
                # At least one child is empty
                # Target node is replaced by either non-empty child or None
                root = root.left if root.left else root.right

            else:
                # Both two childs exist
                # Target node is replaced by smallest element of right subtree
                cur = root.right

                while cur.left:
                    cur = cur.left

                root.val = cur.val
                root.right = self.deleteNode( root.right, cur.val )
                    
        return root

結語

好，今天一口氣介紹了最精華的部分，

通用的Binary search Tree 二元搜索樹的框架，
還有相關的衍伸變化題與演算法建造流程，

希望能幫助讀者、觀眾徹底理解它的原理，

並且能夠舉一反三，洞察其背後的本質！

感謝收看囉! 我們下篇文章再見~