方法介绍：

通过二叉查找树保存Key，实现快速查找
还有散列表法（散列及解决冲突），与有序表法（二分查找）

BST定义：

左子树节点key比根节点来的小，右子树节点key比根节点大。

image.png

可以看出，根据插入值的顺序，生成的BST树也不一样。不是完全有序。

BST方法介绍：

1. put、get方法：
   插入BST中，创建新节点。
   没啥可说的，注意递归，递归结束条件为找到合适的位置，put创建树节点加入到子节点中去；get方法将找到的节点return。

2. delete方法：
   移除当前BST的某个节点。
   ①先通过get方法去找key，找到需要删除的节点。
   ②判断节点是否为叶节点，若为叶节点，直接删除（令叶节点为None）
   ③若有左右子节点，则去找后继节点
   后继节点法：通过看删除节点的右子节点中最小的那个节点（取最靠近待删除节点的值取代删除的节点值。）找到后继节点后，拆除待删除节点并放入后继节点
   拆除方法：若后继节点为叶节点直接摘除；如果不是，由于后继节点肯定是左节点，且肯定只有右子节点，将后继节点的右节点放在后继节点父节点的左节点。

   
   image.png
   

   ④如果只有左节点或者右节点
   一、 如果被删除的节点有左子节点：若被删除的节点是左子节点，则删除；右子也是一样；如果被删除的节点是根节点，则直接去他的左子节点替换。
   二、 如果被删除的节点有右子节点：同上

算法分析：

查找算法复杂度：如果随机分布，则两边平均分布key值大致相等
put方法的复杂度为O(log2n)

AVL树概念：

AVL树的定义（平衡二叉查找树）：
对每个节点引入平衡因子参数
平衡因子：左右子树的高度差。

AVL树平衡因子为0，-1，1

AVL树搜索的时间复杂度：O(logn)

image.png

AVL树方法：

1. 新key以叶节点插入BST
2. 重新平衡，并修改父节点的平衡因子（左重或者右重，进行旋转重新平衡AVL树），
   直到两种情况：①根节点②父节点的平衡因子被调整为0
   旋转方法如下：
   1.左重，右旋
   2.右重，左转，如果右子节点不存在左重，
   则如下图，把右子节点B变为根节点，将A作为B的左子节点，若原B有左子节点，则把该节点挂在A的右子节点处。
   更新父节点引用，并更新平衡因子

image.png
image.png

如果右子节点存在左重
则先进行右旋，在实施左旋

image.png

右旋的代码类似左旋

总体代码如下：

# BST树的构建
class BinarySearchTree:
    def __init__(self):
        # 引用根节点TreeNode类
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    # 迭代器 实现 for key in tree
    def __iter__(self):
        return self.root.__iter__()

    # 插入key，构造BST
    def put(self, key, val):
        if self.root:
            self._put(key, val, self.root)
        else:
            self.root = TreeNode(key, val)
        self.size += 1

    def _put(self, key, val, currentNode):
        if key < currentNode.key:
            if currentNode.hasleftchild():
                self._put(key, val, currentNode.leftchild)
            else:
                currentNode.leftchild = TreeNode(key, val, parent=currentNode)
        else:
            if currentNode.hasrightchild():
                self._put(key, val, currentNode.rightchild)
            else:
                currentNode.rightchild = TreeNode(key, val, parent=currentNode)

    # 索引赋值：实现 mytree[key] = value
    def __setitem__(self, key, value):
        self.put(key, value)

    # 在二叉树中找到key所在的节点并取值
    def get(self, key):
        if self.root:
            res = self._get(key, self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None

    def _get(self, key, currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key, currentNode.leftchild)
        else:
            return self._get(key, currentNode.rightchild)

    # AVL树的方法：
    '''def _put(self, key, val, currentNode):
        if key < currentNode.key:
            if currentNode.hasleftchild():
                return self._put(key, val, currentNode.leftchild)
            else:
                currentNode.leftchild = TreeNode(key, val, parent=currentNode)
                # 更新平衡因子
                self.updateBalance(currentNode.leftchild)
        else:
            if currentNode.hasrightchild():
                return self._put(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)
            return
        # 如果在-1至1之间，平衡，看是否有父节点，如果有，调整父节点
        if node.parent is not None:
            if node.isleftchild():
                node.parent.balancefactor += 1
            elif node.isrightchild():
                node.parent.balancefactor -= 1
            # 调整以后的父节点平衡因子不为0，则再调整父节点的父节点平衡因子
            if node.parent.balancefactor != 0:
                self.updateBalance(node.parent)

    # 左旋的方法
    def rotateLeft(self, rotRoot):
        newRoot = rotRoot.rightchild
        rotRoot.rightchild = newRoot.leftchild
        if newRoot.leftchild is not None:
            newRoot.leftchild.parent = rotRoot
        newRoot.parent = rotRoot.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)
        rotRoot.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)
            else:
                self.rotateLeft(node)
        elif node.balancefactor > 0:
            if node.leftchild.balancefactor < 0:
                self.rotateLeft(node.leftchild)
                self.rotateRight(node)
            else:
                self.rotateRight(node)'''

    # 索引取值 实现 value = mytree[key]
    def __getitem__(self, key):
        return self.get(key)

    # 寻找索引 实现 key in mytree
    def __contains__(self, key):
        if self._get(key, self.root):
            return True
        else:
            return False

    # 迭代器实现 实现 for key in tree
    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

    # 删除方法
    def delete(self, key):
        if self.size > 1:
            node_to_remove = self._get(key, self.root)
            if node_to_remove:
                self.remove(node_to_remove)
                self.size -= 1
            else:
                raise KeyError('error, key not in tree')
        elif self.size == 1 and self.root.key == key:
            self.root = None
            self.size -= 1
        else:
            raise KeyError('error, key not in tree')

    # 实现方法 del tree(key)
    def __delitem__(self, key):
        self.delete(key)

    def remove(self, currentNode):
        # 判断节点是否为叶节点，若为叶节点，直接删除（令叶节点为None）
        if currentNode.isleaf():
            if currentNode == currentNode.parent.leftchild():
                currentNode.parentchild.leftchild = None
            else:
                currentNode.parentchild.rightchild = None
        else:
            if currentNode.hasbothchildren():
                 # 后继节点法：通过看删除节点的右子节点中最小的那个节点（取最靠近待删除节点的值取代删除的节点值。）找到后继节点后，拆除待删除节点并放入后继节点
                succ = currentNode.findsuccessor()
                succ.spliceOut()
                currentNode.key = succ.key
                currentNode.payload = succ.payload

            elif currentNode.hasleftchild():
                # 如果被删除的节点有左子节点
                if currentNode.isleftchild():
                    currentNode.leftchild.parent = currentNode.parent
                    currentNode.parent.leftchild = currentNode.leftchild
                elif currentNode.isrightchild():
                    currentNode.leftchild.parent = currentNode.parent
                    currentNode.parent.rightchild = currentNode.leftchild
                else:
                    currentNode.replacenodedata(currentNode.leftchild.key,
                                                currentNode.leftchild.payload,
                                                currentNode.leftchild.leftchild,
                                                currentNode.leftchild.rightchild)
            else:
                # 如果被删除的节点有右子节点
                if currentNode.isleftchild():
                    currentNode.rightchild.parent = currentNode.parent
                    currentNode.parent.leftchild = currentNode.rightchild
                elif currentNode.isrightchild():
                    currentNode.rightchild.parent = currentNode.parent
                    currentNode.parent.righchild = currentNode.rightchild
                else:
                    currentNode.replacenodedata(currentNode.rightchild.key,
                                                currentNode.rightchild.payload,
                                                currentNode.rightchild.leftchild,
                                                currentNode.rightchild.rightchild)

    # 找到后继节点
    def findsuccessor(self):
        succ = None
        if self.hasrightchild():
            succ = self.rightchild().findmin()
        else:
            '''if self.parent:
                if self.isleftchild():
                    succ = self.parent
                else:
                    self.parent.rightchild = None
                    succ = self.parent.findsuccessor()
                    self.parent.rightchild = self'''
        return succ

    # 找到最小值节点
    def findmin(self):
        current = self
        while current.hasleftchild():
            current = current.leftchild
        return current

    # 将前面找到的节点摘出
    def spliceOut(self):
        # 若后继节点为叶节点直接摘除
        if self.isleaf():
            if self.isleftchild():
                self.parent.leftchild = None
            '''else:
                self.parent.rightchild = None'''

        elif self.hasanychildren():
            if self.hasleftchild():
                '''if self.isleftchild():
                    self.parent.leftchild = self.leftchild
                else:
                    self.parent.rightchild = self.leftchild
                self.leftchild.parent = self.parent'''
        else:
            # 由于后继节点肯定是左节点，且肯定只有右子节点，将后继节点的右节点放在后继节点父节点的左节点。
            if self.isleftchild():
                self.parent.leftchild = self.rightchild
            else:
                '''self.parent.rightchild = self.rightchild'''
            self.rightchild.parent = self.parent


# 树节点定义，BST需要引用树节点类
class TreeNode:
    def __init__(self, key, val, left=None, right=None, parent=None):
        self.key = key
        # key值对应存储的实际值
        self.payload = val
        self.leftchild = left
        self.rightchild = right
        self.parent = parent

    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.rightchild or self.leftchild)

    def hasanychildren(self):
        return self.rightchild or self.leftchild

    def hasbothchildren(self):
        return self.rightchild and self.leftchild

    def replacenodedata(self, key, val, lc, rc):
        self.key = key
        self.payload = val
        self.leftchild = lc
        self.rightchild = rc
        if self.hasleftchild():
            self.leftchild.parent = self
        if self.hasrightchild():
            self.rightchild.parent = self