AVL树 编辑
AVL树是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是



O



{\displaystyle O}

。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
1
相关
平衡二叉搜索树是一种结构平衡的二叉搜索树，它是一种每个节点的左右两子树高度差都不超过一的二元树。它能在大O符号内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。
平衡二叉搜索树是一种结构平衡的二叉搜索树，它是一种每个节点的左右两子树高度差都不超过一的二元树。它能在大O符号内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。
平衡二叉搜索树是一种结构平衡的二叉搜索树，它是一种每个节点的左右两子树高度差都不超过一的二元树。它能在大O符号内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。