AVL树是由GM Adelson - Velsky和EM Landis于1962年发明的。为了纪念其发明者,这树结构被命名为AVL。
AVL树可以定义为高度平衡二叉搜索树,其中每个节点与平衡因子相关联,该平衡因子通过从其左子树的子树中减去其右子树的高度来计算。
如果每个节点的平衡因子在-1
到1
之间,则称树是平衡的,否则,树将是不平衡的并且需要平衡。
平衡系数(k)=高度(左(k)) - 高度(右(k))
如果任何节点的平衡因子为1
,则意味着左子树比右子树高一级。
如果任何节点的平衡因子为0
,则意味着左子树和右子树包含相等的高度。
如果任何节点的平衡因子是-1
,则意味着左子树比右子树低一级。
AVL树如下图所示。 可以看到,与每个节点相关的平衡因子介于-1
和+1
之间。 因此,它是AVL树的一个例子。
复杂性
算法 | 平均情况 | 最坏情况 |
---|---|---|
空间 | o(n) | o(n) |
搜索 | o(log n) | o(log n) |
插入 | o(log n) | o(log n) |
删除 | o(log n) | o(log n) |
AVL树上的操作
由于AVL树也是二叉搜索树,所有操作都以与在二叉搜索树中执行的相同方式执行。 搜索和遍历不会导致AVL树违反属性。 但是,插入和删除操作可能会违反此属性,因此树可能需要平衡。
编号 | 操作 | 说明 |
---|---|---|
1 | 插入 | AVL树中的插入的执行方式与在二叉搜索树中执行的方式相同。但是,它可能会导致违反AVL树属性,因此树可能需要平衡。可以通过应用旋转来平衡树。 |
2 | 删除 | 删除也可以按照在二叉搜索树中执行的相同方式执行。 删除也可能会扰乱树的平衡,因此,使用各种类型的旋转来重新平衡树。 |
为什么要使用AVL树
AVL树通过不让它倾斜来控制二叉搜索树的高度。 高度为h
的二叉搜索树中的所有操作所花费的时间是O(h)
。 但是,如果二叉搜索树变得偏斜(即最坏的情况),它可以扩展到O(n)
。 通过将该高度限制为log n
,AVL树将每个操作的上限强加为O(log n)
,其中n
是节点的数量。