注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

AVL树介绍与实现[原创]  

2011-01-26 05:55:23|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  1. 什么是AVL树

    AVL 树是一种二叉排序树,但是它能保持自身的高度平衡,这使得的树的查找与插入都很快,当然为了维持树的平衡在树节点插入与删除过程中也要做一些维持树本身平衡的操作。AVL树是由前苏联人G.M. Adelson-Velskii and E.M. Landis 1962年共同发明的,这种结构是计算机科学中发明的第一个有自平衡特性的数据结构,有着开创意义,为后来发明的2-4树、红黑树,AA树等指出了方向,这种设计思想有着很重要的意义。因为后来设计的更加复杂的数据结构如红黑树在平均性能上超过了AVL树,因此AVL树直接应用场合己不多见,但是学习它其中的优秀设计思想对提高自己的水平还是有很重要的意义,如果想了解红黑树可以查看我以前写的一篇关于红黑树的日志,地址如下:

    http://saturnman.blog.163.com/blog/static/5576112010969420383/

    本文是我在知道什么时候是AVL树后自己推导树的插入与删除算法的,整个算法和代码都没见得优雅和有效率,写这个总结只是为了练习自己的分析数据结构的能力,如果读本人者想找一种优雅而高效的实现,那请自行google查寻之。

    1. AVL树定义:
      1. 树是一棵二叉查找树
      2. 定义树的平衡因子为右子树的高度减去左子树的高度,那么树的平衡因子只能为-1 0 或1。

    示例:下面是一棵AVL树从0个结点到时20个结点的构建全过程

    

  1. AVL 树的实现细节
  2. 设计思想与应用

Ref:

PS:

有些事情想起来简单,做起来还真有些麻烦。通过实现这个东西又学会不少gdb的知识,gdb真是利器,而且还有ddd数据显示功能实在太酷了,有了它真是事半倍功倍。想实现红黑树时用gdb调试的真是要命,还好我自己设计算法把树实时显示成图片,唉,有句话说的好,没有退路就只能找出路。下面上几张gdb和ddd的酷图。

  评论这张
 
阅读(3099)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017