再回首数据结构—AVL树(一)
前面所讲的二叉搜索树有个比较严重致命的问题就是极端情况下当数据以排序好的顺序创建搜索树此时二叉搜索树将退化为链表结构因此性能也大幅度下降,因此为了解决此问题我们下面要介绍的与二叉搜索树非常类似的结构就诞生了;
AVL(Adelson-Velskii and Landis)树,名字取自其发明者 G.M. Adelson-Velsky 和 E.M. Landis的首字母,AVL树是一棵特殊的二叉搜索树它与普通二叉搜索树最主要的区别就是其能够使二叉搜索树维持其左右节点的平衡;
AVL树:其任意一个节点左子树与右子树高度差不超过1,由于此特征因此需要在AVL增删节点时维护其左右节点使该树满足该特性(左右节点平衡);
此AVL树中节点2节点高度都为2,节点1与3节点高度都为1;节点高度为左右子树中最大的节点高度+1;
AVL树实现关键
1、标注其节点高度
2、计算节点平衡因子
3、维护其节点满足左右节点高度不超过1
AVL树的实现
1、AVL树定义
根据AVL树的特性先定义该数据类型的结构;
type AVL struct {
root *AVLNode
size int
compare Comparable
}
type AVLNode struct {
e interface{}
left *AVLNode
right *AVLNode
height int
}
AVL:为定义的AVL树自定义对象
AVLNode:为树中每个节点的节点自定义对象
compare:为定义的用于树中节点元素进行数据对比的对象
size:AVL树的元素个数
root:树的根节点
e:节点元素值
left:左子树
right:右子树
height:节点高度
AVL树与二叉搜索树一样所有很多操作都可用递归来实现,比如元素的添加、删除、查找等;
可以说AVL树为二叉搜索树的升级版本所以并不会像出现二叉搜索树一样出现退化为O(n)时间复杂度的情况,与二叉搜索树一样通过中序遍历可得到排序好的数据,二叉搜索树的搜索、插入、删除时间复杂度为O(log(n)),n为树的深度,这里只是简单的介绍了AVL树,后面会有AVL树实现的相关介绍;
文章首发地址:Solinx
http://www.solinx.co/archives/1323
最新文章
- 旷世奇坑!!!spring 不能自动注入
- Chapter 2: Design the user experience
- if分支练习
- linux中断的上半部和下半部 【转】
- Javascript 的类型转换之减号
- IDEA快速光标跳转
- Chapter 1 Securing Your Server and Network(11):使用透明数据库加密
- 使用SVG基本操作API
- NOIP2014-5-24模拟赛
- C#使用WebClient下载文件到本地目录
- 使用Node.js的Express框架进行文件上传
- Spring history&;Design Philosophy 简单介绍~
- JS性能优化 之 事件委托
- 084 HBase的数据迁移(含HDFS的数据迁移)
- [JetBrains注册] 利用教育邮箱注册JetBrains产品(pycharm、idea等)的方法
- C#代码覆盖率实践-vsinstr和OpenCover
- C++中文件读写的操作
- Mvc4_mvc4跟mysql语法
- git2
- yum安装docker报 No package docker available错误
热门文章
- centos7.3下安装redis3.2 yum安装
- JS正则表达式一些基本使用、验证、匹配、正则匹配时一个变量
- org.springframework.dao.DataIntegrityViolationException: could not execute statement; SQL [n/a]; constraint [null]; nested exception is org.hibernate.
- 让ubuntu的ssh保持长时间连接
- LaTex 2
- mysql根据某个字段分组根据更新时间获取最新的记录
- Java工程路径及相对路径(转载)
- uiautomator 1使用简介
- 通过tomcat shutdown port关闭tomcat
- 菜鸟学配置vim