如何快速掌握5分钟AVL树入门知识？

本文共计2161个文字，预计阅读时间需要9分钟。

在计算机科学中，AVL树是最先提出的一种自平衡二叉查找树，也是其他二叉查找树的基础。它带有平衡条件，每个节点都确保左右子树的高度差不超过1。

在计算机科学中，AVL树是最先发明的自平衡二叉查找树，也是其他二叉查找树的基础

转载请注明出处：www.cnblogs.com/morningli/p/16033733.html

AVL树是带有平衡条件的二叉查找树，其每个节点的左子树和右子树的高度最多相差1。为了保持AVL树始终平衡，每次插入和删除都需要进行额外的平衡操作。

上面两个二叉搜索树，A是AVL树，而B不是。

为什么需要平衡二叉树？

二叉搜索树一定程度上可以提高搜索效率，但是因为二叉树没有对树的形状进行限制，很容易就退化成了一个链表，搜索效率降低为 O(n)。

这里说明会导致二叉搜索树退化的两种原因：

1、插入的数据是有序地，比如先后插入1,2,3,4,5，会产生下面的二叉搜索树：

2、因为二叉搜索树的删除操作总是用右子树的节点替换被删除的节点，所以在不断的插入删除后，左子树会比右子树更深。现在已经证明，如果交替插入和删除O(N²)次，那么树的期望深度将是O(√N)。

为了避免二叉查找树搜索效率的恶化，我们需要对二叉树的深度进行限制，避免过深的二叉搜索树。

一种解决办法是要有一个称为平衡（balance）的附加结构条件：任何节点的深度均不可以过深。AVL树就是这样的加了平衡条件的最古老的平衡查找树。

另一种办法是不对树的深度做限制，但是每次操作都对树做一些调整，使后面的操作效率更高，保证连续M次操作在最坏的情况下花费O(MlogN)的时间。