数据结构笔记总结(11.1)平衡二叉树和AVL

回忆二分搜素树的问题

二分搜素树存在一个严重的问题,就是如果数据是顺序添加进二分搜素树的,如下图所示按照1,2,3,4,5,6,的顺序创建二叉树的话,整个二分搜素树将退化为一个链表,它会大大降低二分搜素树的效率。

解决办法:在现有的二分搜素树基础上添加一定的机制使得二分搜素树能够维持平衡二叉树的性质

AVL树

这个名称是根据两个发明人的首字母缩写来命名的,在1962年的论文中首次提出,是最早的自平衡二分搜素树结构。

什么叫做平衡二叉树?

一棵满的二叉树(除了叶子节点以外所有其他节点都有左右两个子树)一定是平衡二叉树,在满二叉树的情况下,可以让整个二叉树的高度达到最低的状态。

但是通常我们的数据不可能正好填满二叉树,在之前讲堆的时候,引入过完全二叉树。

对于一棵完全二叉树可以理解成把多个元素按照二叉树的形状一层层的铺开,最终得到的结果就是一棵完全二叉树。

对于完全二叉树来说,有可能有一个非叶子节点右子树是空的(比如16),但是它孔空缺的部分一定是在整棵树右下部分。

对于完全二叉树,整棵树的叶子节点最大的深度值和最小的深度值相差不会超过1,也就是说所有的叶子节点要么在这棵树的最后一层,要么在倒数第二层。

[v_notice]对于任意一个节点,左子树和右子树的高度差不能超过1[/v_notice]

[v_notice]平衡二叉树的高度和节点数量之间的关系也是O(logn)的[/v_notice]

如图,通过标注节点的高度并计算平衡因子得出:该二叉树不是平衡二叉树。

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(11.1)平衡二叉树和AVL

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多