二叉查找樹(Binary Search Tree)的python實作及算法分析

二叉查找樹（BST）

特點：比父節點小的key都出現在左子樹，比父節點大的key都出現在右子樹。

二叉查找樹的python實作

class BinarySearchTree(object):   
    def __init__(self, key):    ##初始化
        self.key = key
        self.left = None
        self.right = None

    def find(self, x):   
        if x == self.key:
            return True
        elif x < self.key and self.left:  # 如果x小，則去左子樹找
            return self.left.find(x)
        elif x > self.key and self.right:  # 如果x大，則去右子樹找
            return self.right.find(x)
        else:
            return None  # 找不到傳回None

    def findMin(self):
        if self.left:  # 如果左節點存在，最小值一定在左節點的最深處
            return self.left.findMin()
        else:
            return self.key  # 如果左節點沒有，那麼根節點最小

    def findMax(self):
        if self.right:  # 如果右節點存在，最大值一定在右節點的最深處
            return self.right.findMax()
        else:
            return self.key  # 如果右節點沒有，那麼根節點最大

    def insert(self, x):
        if self.find(x):  # 如果找到了該節點，則什麼也不做
            return None
        else:  # 如果沒有找到則開始插入
            if x < self.key:  # 如果插入值小，則插入左子樹
                if self.left:  # 先判斷左子樹是否存在
                    return self.left.insert(x)
                else:
                    newTree = BinarySearchTree(x)
                    self.left = newTree  # 如果左子樹不存在，則把該節點設為左子樹
            elif x > self.key:  # 如果插入值大，則插入右子樹
                if self.right:
                    return self.right.insert(x)
                else:
                    newTree = BinarySearchTree(x)
                    self.right = newTree

    def delete(self, x):
        if self.find(x):  # 首先判斷該節點是否存在
            if x < self.key:  # 如果要删的資料比該資料self.key小，從左子樹删起
                self.left = self.left.delete(x)
                return self
            elif x > self.key:  # 如果要删的資料比self.key大，從右子樹删起
                self.right = self.right.delete(x)
                return self
            else:  # 如果就是該資料，判斷他是否有左右子樹
                if self.left and self.right:  # 如果左右子樹都存在
                    minkey = self.right.findMin().key  # 把右子樹中最小的點連接配接原來x的父節點, 并且右子樹中删除該點
                    self.key = minkey
                    self.right = self.right.delete(minkey)
                    return self
                else:  # 如果左右節點不全存在
                    if self.left:
                        return self.left
                    else:
                        return self.right
        else:
            return self


bst = BinarySearchTree(17)
node_list = [17, 5, 29, 38, 35, 2, 9, 8, 16, 11]
for l in node_list:
    bst.insert(l)
print(bst.findMax())
print(bst.findMin())
print(bst.find(10))
print(bst.delete(11))

           

算法分析：

（1）二叉查找樹的性能決定因素在于二叉搜尋樹的高度(最大層次），而高度又受資料項key插入順序的影響。

（2）若key的清單是随機分布的話，那麼兩側的鍵值大緻相等

（3）BST的高度就是log2 n，n是節點的個數，而且該樹是平衡樹

平衡二叉查找樹（AVL樹）

特點：能夠在key插入是一直保持平衡的二叉查找樹。

在AVL實作中，需要對每個節點跟蹤“平衡因子”參數，其定義為左右子樹的高度差。AVL樹的平衡因子都在-1，0，1之間，

AVL樹的python實作

1.AVL樹的實作，周遊與查找操作與二叉查找樹相同。

見上面

2.AVL樹的插入操作

插入一個節點可能會破壞AVL樹的平衡，可以通過旋轉操作來進行修正。插入一個節點後，隻有從插入節點到根節點的路徑上的節點的平衡可能被改變。

def put(self,key):
        if not self.root:
            self.root=Node(key)
        else:
            self.root=self._put(key,self.root)
    def _put(self,key,node):
        if node is None:
            node=Node(key)
        elif key<node.key:
            node.left=self._put(key,node.left)
            if (self.height(node.left)-self.height(node.right))==2:
                if key<node.left.key:
                    node=self.singleLeftRotate(node)
                else:
                    node=self.doubleLeftRotate(node)
            
        elif key>node.key:
            node.right=self._put(key,node.right)
            if (self.height(node.right)-self.height(node.left))==2:
                if key<node.right.key:
                    node=self.doubleRightRotate(node)
                else:
                    node=self.singleRightRotate(node)
        
        node.height=max(self.height(node.right),self.height(node.left))+1
        return node
           

算法分析：經過複雜的put方法，AVL樹始終能維持平衡，get也始終保持O(log n)的高性能。

AVL樹的put方法的時間複雜度還是O((log n)