二叉查找树(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)