• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

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

极客笔记 Geekerstar 10个月前 (07-11) 480次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

回忆二分搜素树的问题

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

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

AVL树

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

什么叫做平衡二叉树?

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

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

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

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

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

对于任意一个节点,左子树和右子树的高度差不能超过1
平衡二叉树的高度和节点数量之间的关系也是O(logn)的

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

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(11.1)平衡二叉树和AVL
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00