数据结构之AVL树
2023-03-09 22:24:21 时间
树的平衡,我们已经知道DWL算法,不过DWL算法需要从整体上平衡树,但是树的平衡也可以局部的进行,由Adel'son-Vel'skii-Landis提出了一种经典方法,称为AVL树。
1。概念:AVL树,或者说可适应树,是指树中每个节点的的平衡因子的绝对值不大于1,即只能为-1,0,1
平衡因子:节点的右子树的高度减去左子树的高度
2。AVL树的插入:从新插入节点到根的路径上,修改遇到的节点的平衡因子即可,对其他部分没影响
1)向右子女的右子树插入一个节点,单旋转就可以
2)向右子女的左子树插入一个节点,双旋转,先围绕父节点,再围绕祖父节点
3。AVL树的删除:从删除节点到根的路径上,任何不平衡因子的节点都需要修改,与插入不同,需要O(lgn)次旋转。
4。一个java实现:
http://www.koders.com/java/fid3B5247D34968077A6EFD4216589026D343559FF9.aspx?s=avl%2Btree
文章转自庄周梦蝶 ,原文发布时间5.17
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的