一、AVL树平衡二叉树的由来查找、插入、删除平均 / 最坏时间复杂度均为 O(logn)AVL平衡二叉树树首先是一个BST二叉搜索树树因为BST树进行大量的插入和删除操作可能会导致BST树退化所以我们为了避免其退化从而在BST树插入和删除操作执行之后多加一个平衡操作相当于一旦发现其有劣化的趋势则立刻通过旋转操作将其优化一下二、AVL的定义避免BST树的劣化AVL树对于平衡的定义AVL认为所有的节点的左右子树的高度差不能超过1平衡因子左子树高度-右子树高度通过旋转操作将失衡变成平衡单旋单左旋LL型单左旋RR型单右旋LR型第一次旋转是对失衡节点的孩子 第二次旋转对失衡节点自身RL型失衡三、AVL树的删除非递归逻辑1.先调用查找函数去查找待删除节点是否存在2.如果不存在则直接结束无需调整3.如果存在该节点则按照BST逻辑先去判断该待删除节点是什么类型3.1 判断该节点是双分支 狸猫换太子3.2 如果该节点是单分支 直接让其父节点指向其孩子节点3.3 如果该节点是零分支 直接让其父节点抓向其节点的手置为NULL即可AVL删除非递归逻辑1.判断当前root是否存在2.如果当前root等于NULL则说明待删除节点不存在或者当他存在只不过被我们释放掉了直接返回NULL让上一层来接受3.如果当前root不等于NULL则说明存在则将其root-data和待删除val比较4.此时待删除val值节点删除完之后返回值被上一层root接收之后只需要对接收的root做两件事即可4.1更新root高度4.2调用Rotate通用旋转函数去给root做检查
