二叉查找樹，AVL，紅黑樹的Python實作

簡介：本文重點給出面試高頻二叉樹的實作

二叉查找樹，顧名思義，就是用于輔助我們進行查找的樹狀資料結構，

在講本文的主角之前，先講一下其他與查詢相關的資料結構，

首先，無序表，查找的時間復雜度為O(n).

有序表（預排序），查找（二分查找）的時間復雜度為O(logn),但是插入和洗掉的時間復雜度為O(n)

那如何降低插入和洗掉的時間復雜度呢，我們本文的主角就登場了

一、二叉查找樹（二叉搜索樹/二叉排序樹，它的稱呼比較多）

定義：一棵二叉查找樹是一棵二叉樹，其中每個結點都包含一個鍵（以及相關聯的值）且每個結點的鍵都大于其左子樹中的任意結點的鍵而小于右子樹的任意結點的鍵，

它能夠實作O(logn)的查找平均時間復雜度，且插入和洗掉的平均時間復雜度也為O(logn).

先給出二叉搜索樹結點的定義

class BSTNode:
    """樹的結點"""
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

再給出二叉搜索樹的實作

class BST:
    """二叉搜索樹"""

    def __init__(self):
        self.root = None
        
    def find(self, val):
        """查找方法，回傳布林值"""
        return self._find(self.root, val)
    
    def _find(self, node, val):
        if node is None:
            return False
        if node.val == val:
            return True
        if val<node.val:
            return self._find(node.left,val)
        else:  
            return self._find(node.right,val)
        
    def insert(self, val):
        """插入方法，當前二叉搜索樹定義為不包含重復key的樹，所以當插入重復key時會失敗"""
        if self.find(val):
            return False
        if not self.root:
            self.root = node=BSTNode(val)
        else:
            self._insert(self.root, val)
        return True
    
    def _insert(self, node, val):
        if not node: 
            node=BSTNode(val)
        else:
            if val<node.val:
                node.left=self._insert(node.left,val)
            elif val>node.val:
                node.right=self._insert(node.right,val)
        return node
  
    def findmin(self):
        """查找key值最小的結點并回傳該結點"""
        if not root:
            return None
        else:
            return self._findmin(self.root)
    
    def _findmin(self, node):
        if node.left:
            return self._findmin(node.left)
        else:
            return node
    
    def delete(self, val):
        """洗掉，回傳布林值"""
        if not self.find(val):
            return False
        else:
            self._delete(self.root, val)
            return True
    
    def _delete(self, node, val):
        """洗掉方法，最為復雜"""
        if not node: 
            return None
        if val<node.val:
            node.left = self._delete(node.left,val)
        elif val>node.val:
            node.right = self._delete(node.right,val)
        else:
            #當待洗掉結點有左右孩子時，選擇左子樹最大結點或者右子樹最小節點用來替換該節點的值
            if node.left and node.right:
                node.val=self._findmin(node.right).val
                #替換完成后把對應的左子樹最大節點或者右子樹最小節點進行遞回洗掉
                node.right = self._delete(node.right,node.val)
            else:
                #當待洗掉結點只有一個孩子時，直接用孩子替換該結點
                node = node.left if not node.right else node.right
        return node

問題：在極端情況下，比如二叉查找樹的所有節點只有左子樹的情況，所有操作的時間復雜度都會變為O(n)，根本原因是二叉樹的結構不平衡，、

二、AVL樹

為了解決二叉查找樹不平衡情況下糟糕的時間復雜度，我們在其基礎上增加了一個約束：每個結點的左右子樹的高度差不能大于1，具備該條件的二叉查找樹即為AVL樹

AVL樹保證了查找、插入、洗掉的最差時間復雜度均為O(logn)

class AVLNode:
    """樹的結點"""
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = None

class AVL:
    """二叉平衡樹之AVL"""
    def __init__(self):
        self.root = None
    
    def _height(self, node):
        """回傳當前結點的高度"""
        return -1 if not node.height else node.height
    
    def find(self, val):
        return self._find(self.root, val)
    
    def _find(self, node, val):
        if not node:
            return False
        elif val == node.val:
            return True
        elif val < node.val:
            return self._find(node.left, val)
        else:
            return self._find(node.right, val)
    
    def insert(self, val):
        if self.find(val):
            return False
        if not self.root:
            self.root = AVLNode(val)
        else:
            self._insert(self.root, val)
        return True
    
    def _insert(self, node, val):
        if not node:
            node = AVLNode(val)
        elif val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return self._balance(node)
    
    def _balance(self, node):
        """對結點進行高度平衡"""
        if not node:
            return node
        if self._height(node.left)-self._height(node.right)>1:
            if self._height(node.left.left)>self._height(node.left.right):
                self._rotate_single_left(node)
            else:
                self._rotate_double_left(node)
        elif self._height(node.right)-self._height(node.left)>1:
            if self._height(node.right.right)>self._height(node.right.left):
                self._rotate_single_right(node)
            else:
                self._rotate_double_right(node)
        node.height = max(height(node.left), height(node.right))+1
        return node
    
    def _rotate_single_left(self, node):
        new_node = node.left
        node.left = new_node.right
        new_node.right = node
        node.height = max(self._height(node.left), self._height(node.right))+1
        new_node.height = max(self._height(new_node.left), self._height(new_node.right))+1
        return new_node
    
    def _rotate_single_right(self, node):
        new_node = node.right
        node.right = new_node.left
        new_node.left = node
        node.height = max(self._height(node.left), self._height(node.right))+1
        new_node.height = max(self._height(new_node.left), self._height(new_node.right))+1
        return new_node
    
    def _rotate_double_left(self, node):
        node.left = self._rotate_single_right(node.left)
        return self._rotate_single_left(node)
    
    def _rotate_double_right(self, node):
        node.right = self._rotate_single_left(node.right)
        return self._rotate_single_right(node)
    
    def remove(self, val):
        if not self.find(val):
            return False
        else:
            self.remove(self, self.root, val)
            return True
    
    def findmin(self):
        return self._findmin(self.root)
    
    def _findmin(self, node):
        if node.left:
            return self._findmin(node.left)
        else:
            return node
        
    def _remove(self, node, val):
        if not node:
            return None
        if val < node.val:
            self._remove(node.left, val)
        elif val > node.val:
            self._remove(node.right, val)
        else:
            if node.left and node.right:
                node.val = self._findmin(node.right).val
                node.right = self._remove(node.right, node.val)
            else:
                node = node.left if not node.right else node.right
        return self._balance(node)

我們仔細分析一下，查詢所用時間復雜度都耗費在遞回程序上，為O(logn)

插入所用時間復雜度耗費在遞回（logn）和旋轉，所以插入時間復雜度O(logn)

洗掉所用時間復雜度耗費在遞回（logn）和旋轉（至多logn次，當洗掉結點導致根節點高度不平衡時，需要從當前結點到根節點的路徑上遞回進行平衡），總的洗掉時間復雜度為O(logn)

問題：我們可以看出，在所有程序中，洗掉程序中的旋轉是相對最耗費時間的，那我們有沒有辦法減少總的旋轉次數呢？

三、紅黑樹

針對上述問題，我們思考，之所以旋轉次數多是因為AVL的平衡條件過于苛刻（左右子樹之差小于等于1），我們能不能通過放寬這個限制來取得更加優秀的洗掉效率呢，當然可以，那就是接下來要講的紅黑樹，

紅黑樹通過著色的方式實作2-3樹（關于2-3樹可以看書，不具體介紹了），紅黑樹規定紅色鏈接必為左連接，紅色鏈接連接的兩個點構成一個3-結點，

class RBTNode:
    def __init__(self, val, color, n):
        self.val = val
        self.color = color
        self.left = None
        self.right = None

class RBT:
    def __init__(self):
        self.root = None
    
    def _left_rotate(self, node):
        """左旋，把紅色右鏈接轉化為左鏈接"""
        new_node = node.right
        node.right = new_node.left
        new_node.left = node
        node.color = 'RED'
        return new_node
    
    def _right_rotate(self, node):
        """右旋，把紅色左鏈接轉化為右鏈接"""
        new_node = node.left
        node.left = new_node.right
        new_node.right = node
        new_node.color = 'RED'
        
    def _flipcolors(self, node):
        """反轉當前結點及其子節點的顏色"""
        if node.color = 'BLACK':
            node.color = 'RED'
            node.left.color = 'BLACK'
            node.right.color = 'BLACK'
        else:
            node.color = 'BLACK'
            node.left.color = 'RED'
            node.right.color = 'RED'
        
    def find(self, val):
        return self._find(self.root, val)
    
    def _find(self, node, val):
        if not node:
            return False
        if node.val == val:
            return True
        elif val < nodel.val:
            return _find(node.left, val)
        else:
            return _find(node.right, val)
        
    def _isred(self, node):
        return True if node.color == 'RED' else False
    
    def insert(self, val):
        if self.find(val):
            return False
        else:
            self._insert(self.root, val)
            return True
        
    def _insert(self, node, val):
        if not node:
            return RBTNode(val, 'RED')
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        self._balance(node)
        
        return node
    
    def _balance(self, node):
        if self._isred(node.right) and not self._isred(node.left):
            node = self._left_rotate(node)
        if self._isred(node.left) and self._isred(node.left.left):
            node = self._right_rotate(node)
        if self._isred(node.left) and self._isred(node.right):
            self._flipcolors(node)
        return node
    
    def delete_min(self):
        if not self._isred(self.root.left) and not self._isred(self.root.right):
            self.root.color = 'RED'
        self.root = _delete_min(self.root)
        if self.root:
            self.root.color = 'BLACK'
    
    def _delete_min(self, node):
        if not node.left:
            return None
        if not self._isred and not self._isred(node.left.left):
            node = self._move_red_left(node)
        node.left = self._delete_min(node.left)
        return self._balance(node)
    
    def delete_max(self):
        if not self._isred(self.root.left) and not self._isred(self.root.right):
            self.root.color = 'RED'
        self.root = self._delete_max(self.root)
        if not self.root:
            self.color = 'BLACK'
    
    def _delete_max(self, node):
        if self._isred(node.left):
            node = self._right_rotate(node)
        if not node.right:
            return None
        if not self._isred(node.right) and not self._isred(node.right.left):
            node = self._move_red_right(node)
        node.right = self._delete_max(node.right)
        return self._balance(node)
    
    def _move_red_right(self, node):
        self._flipcolors(node)
        if not self._isred(node.left.left):
            node = self._right_rotate(node)
        return node
    
    def delete(self, val):
        if not self._isred(self.root.left) and not self._isred(self.root.right):
            self.root.color = 'RED'
        self.root = self._delete(self.root, val)
        if not self.root:
            self.color = 'BLACK'
            
    def _delete(self, node, val):
        if val < node.val:
            if not self._isred and not self._isred(node.left.left):
                node = self._move_red_left(node)
            node.left = self._delete(node.left, val)
        else:
            if self._isred(node.left):
                node = self._right_rotate(node)
            if val == node.val and not node.right:
                return None
            if not self._isred(node.right) and not self._isred(node.right.left):
                node = self._move_red_right(node)
            if val == node.val:
                node.val = self._findmin(node.right).val
                node.right = self._delete_min(node.right)
            else:
                node.right = self._delete(node.right, val)
        return self._balance(node)
    
    def _findmin(self, node):
        if self.left:
            return self._findmin(node.left)
        return node

代碼自己寫的，如有錯誤請指正，

參考：

Algorithm(4th version)

資料結構與演算法——Java語言描述

標籤：其他

上一篇：SAS9.4的問題

下一篇：人臉識別壓力測驗