数据结构—— AVL树

（一） 基础补充 

二叉搜索树(BST)
 定义：
        二叉搜索树（Binary Search Tree），简写BST，是满足某些条件的特殊二叉树。任何一个节点的左子树上的点，都必须小于当前节点。任何一个节点的右子树上的点，都必须大于当前节点。任何一棵子树，也都满足上面两个条件。即对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。另外，在二叉查找树中，是不存在重复节点的。本文中AVL 树和二叉搜索树有很多共同点， AVL 树只是增加了自平衡的部分。

数据结构--- 树_尘 关的博客-CSDN博客  具体请看

（二）解析AVL

AVL来源

    1962年，G. M. Adelson-Velsky 和 Evgenii Landis 在其论文 "An algorithm for the organizational of information" 中首次介绍了 AVL 树这种数据结构。AVL 树作为最早出现的自平衡二叉搜索树，其主要特点是任意节点的两个子树的高度最大差别为1，因此它也被称为高度平衡树。在 AVL 树上执行查找、插入和删除的平均和最坏情况下的时间复杂度都是O(log n)。同时，添加和删除节点时可能需要进行一次或多次的树旋转来保持平衡。—— 某科

AVL树是高度平衡的二叉树。它的特点是: AVL树中任何节点的两个子树的高度最大差别为1。