AVL树是一种平衡二叉搜索树。这篇文章介绍了二叉搜索树。二叉树的搜索、插入和删除时间取决于树的高度。在最坏的情况下,高度为 O(n)。如果一棵树完美平衡——即完全二叉树——它的高度是 log n。我们能维持一棵完美平衡的树吗?是的,但这样做的成本会很高。妥协是维持一棵平衡良好的树——也就是说,每个节点的两个子树的高度大致相同。
AVL 树 非常平衡。 AVL 树于 1962 年由两位俄罗斯计算机科学家 G. M. Adelson-Velsky 和 ??E. M. Landis 发明(因此称为 AVL)。在AVL树中,每个节点的两个子树的高度之差是0或1。可以证明AVL树的最大高度是O(log n)。
在 AVL 树中插入或删除元素的过程与常规二叉搜索树相同,只是在插入或删除操作后可能需要重新平衡树。节点的平衡因子是其右子树的高度减去其左子树的高度。如果节点的平衡因子为 -1、0 或 1,则称该节点是平衡。如果一个节点的平衡因子为 -1,则该节点被视为左重;如果其平衡因子为+1,则被视为右重。
以上就是AVL树的详细内容,更多请关注php中文网其它相关文章!
91资源网站长-冰晨2024-08-27 17:15
发表在:【账号直充】爱奇艺黄金VIP会员『1个月』官方直充丨立即到账丨24小时全天秒单!不错不错,价格比官方便宜
91资源网站长-冰晨2024-08-27 16:15
发表在:2022零基础Java入门视频课程不错,学习一下