Python数据结构——AVL树的基本概念

jiekechoo 发布于2019-07-24 18:26 / 535人阅读

摘要：我们知道，当树变得不平衡时和操作会使二叉搜索树的性能降低到。树实现抽象数据类型就像一个普通的二叉搜索树，唯一不同的是这棵树的工作方式。我们通过比较每个节点的左右子树的高度完成比较。

平衡二叉搜索树

在上一节中我们讨论了建立一个二叉搜索树。我们知道，当树变得不平衡时get和put操作会使二叉搜索树的性能降低到O(n)。在这一节中我们将看到一种特殊的二叉搜索树，它可以自动进行调整，以确保树随时都保持平衡。这种树被称为AVL树，命名源于其发明者：G.M. Adelson-Velskii 和 E.M. Landis。

AVL树实现抽象数据类型Map就像一个普通的二叉搜索树，唯一不同的是这棵树的工作方式。为实现我们的AVL树我们需要在树中的每个节点加入一个平衡因子并跟踪其变化情况。我们通过比较每个节点的左右子树的高度完成比较。更正式地讲，我们定义一个节点的平衡因子为左子树和右子树的高度之差。

$$balanceFactor = height(leftSubTree) - height(rightSubTree)$$

利用以上对平衡因子的定义，如果平衡因子大于零，我们称子树“左重”(left-heavy)。如果平衡因子小于零，那么子树“右重”(right-heavy)。如果平衡因子为零，则树是完全平衡的。为实现AVL树，目的是得到一棵平衡的树，我们定义平衡因子如果是 -1，0 或 1，那么这棵树是平衡的。一旦树中节点的平衡因子超出了这个范围，我们需要有一个把树恢复平衡的过程。图 1 是一个不平衡的“右重”树的例子，其中每个节点都标注了平衡因子。

图 1：一棵标注了平衡因子的不平衡的右重树

AVL树性能

在我们继续进行之前让我们看看引入这个新的平衡因子的结果。我们的要求是，确保树上的平衡因子始终为 -1，0 或 1。我们可以通过对键的操作得到更好的时间复杂度。首先，我们要思考如何利用这个平衡条件去改变最坏情况下的树。有两种可能性需要考虑，左重树和右重树。如果我们考虑树的高度为 0，1，2 和 3，图 2 举出了在新规则下可能出现的最不平衡的左重树的例子。

图 2：最坏情况下的左重AVL树

让我们看看树上的节点的总数。我们看到一棵高度为 0 的树有 1 个节点，一个高度为 1 的树有 1 + 1 = 2 个节点，一个高度为 2 的树有 1 + 1 + 2 = 4 个节点，一棵高度为 3 的树有 1 + 2 + 4 = 7 个节点。概括起来，高度为h的树的节点数（N_h）为：

$$N_h = 1 + N_{h-1} + N_{h-2}$$

可能你很熟悉这个公式，因为它和斐波那契序列非常相似。我们可以利用这个公式通过树中的节点的数目推导出一个AVL树的高度。在我们的印象中，斐波那契数列与斐波那契数的关系为：

$$F_0 = 0
F_1 = 1
F_i = F_{i-1} + F_{i-2} text{ for all } i ge 2$$

数学中一个重要的结果是，随着斐波那契序列的数字越来越大，F_i / F_i−1 越来越接近于黄金比例 Φ：

$$Φ = frac{1 + sqrt{5}}{2}$$

如果你想看到上式的推导过程你可以查阅相关的数学资料。我们简单地将这个方程 F_i 近似为：

$$F_i =Φ^i/sqrt{5}$$

如果利用这种近似我们可以将 N_h 的方程改写为：

$$N_h = F_{h+2} - 1, h ge 1$$

通过黄金比例近似代替斐波那契数列的项我们可以得到：

$$N_h = frac{Φ^{h+2}}{sqrt{5}} - 1$$

如果我们整理这些方程的项，并且两边都以 2 为底取对数，然后求解h，则可以导出：

$$log{N_h+1} = (H+2)log{Φ} - frac{1}{2} log{5}
h = frac{log{N_h+1} - 2 log{Φ} + frac{1}{2} log{5}}{log{Φ}}
h = 1.44 log{N_h}$$

这个推导过程告诉我们，在任何时候我们的AVL树的高度等于树中节点数以 2 为底的对数的常数（1.44）倍。这对我们搜索AVL树来说是好消息因为它限制了搜索的复杂度到O(logN)。

混合云私有云基本概念短信产品基本概念机器学习基本概念超融合架构基本概念

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/37752.html

Python数据结构——AVL树的实现

摘要：一旦子树平衡因子为零，那么父节点的平衡因子不会发生改变。新根的父节点将成为旧根的父节点。因为其他操作都是移动整个子树，被移动的子树内的节点的平衡因子不受旋转的影响。让表示以为根节点的子树的高度。既然，我们已经证明，保持 AVL 树的平衡将会使性能得到很大的提升，那我们看看如何在程序中向树插入一个新的键值。因为所有的新键是作为叶节点插入树的，而新叶子的平衡因子为零，所以我们对新插入的节...

Pink 2019-07-31 12:22 评论0 收藏0
学习JavaScript数据结构与算法 — AVL树

摘要：可以看到，一次左单旋将右侧子树的高度减小了，而左侧子树的高度增加了。如图，对进行右单旋，需要左子树的右子树的高度小于等于左子树的高度，否则不能达到平衡的效果，只是把不平衡性从左边转移到了右边。 AVL树普通二叉搜索树可能出现一条分支有多层，而其他分支却只有几层的情况，如图1所示，这会导致添加、移除和搜索树具有性能问题。因此提出了自平衡二叉树的概念，AVL树（阿德尔森-维尔斯和兰迪斯树...

impig33 2019-08-21 11:31 评论0 收藏0
AVL树的Java实现

摘要：容忍不平衡红黑树的思路的核心是增大了可容忍的高度差，从而实现既保证查询效率，也保证了插入和删除后调整平衡的效率。红黑树的查询效率是略低于树的，但是红黑树通过牺牲了少许查询效率，使插入删除后的调整效率达到了常数级别。定义 Wikipedia - AVL树在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡...

leejan97 2019-08-16 17:13 评论0 收藏0