博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
适度平衡树
阅读量:4991 次
发布时间:2019-06-12

本文共 695 字,大约阅读时间需要 2 分钟。

适度平衡树,是指将树高限制为“渐进地不超过 O(logn)”。

举例:

  • AVL 树:兄弟节点的高度之差不超过 1(1
  • 伸展树;
  • 红黑树;
  • kd-树;

当然这些都可以归入平衡二叉搜索树(BBST,Balanced Binary Search Tree)之列。

1. 旋转调整

最基本的修复手段(使适度平衡),就是将围绕特定点的旋转,实现(中序遍历)等价前提下的拓扑调整。

  • zig 和 zag

zig 和 zag 旋转均属局部操作,仅涉及常数个节点及其之间的连接关系,故均可在常数时间内完成。正因如此,在此后的众多实现二叉搜索树平衡化算法时,它们都是支撑性的基本操作

就与树相关的指标而言,经一次 zig 或 zag 旋转之后:

  • 节点 v 的深度加 1;
  • 节点 c 的深度减 1;

这一局部子树(乃至全树)的高度可能发生变化,但上下幅度均不超过 1 层;

2. AVL 树

通过合理设定适度平衡的标准,并借助以上等价变换,AVL 树(AVL tree)可以实现近乎理想的平衡。在渐进意义下,AVL 树可始终将其高度控制在 O(logn) 以内,从而保证每次查找、插入或删除操作,均可在 O(logn)

从平衡因子(balance factor)的角度来看 AVL 树。任一节点 v 的平衡因子定义为“其左、右子树的高度差”(显然可以为负)。

因此,从平衡因子的角度说,AVL 树是平衡因子受限(|bf|1⇒ bf = -1, 0, 1)的二叉搜索树(BST)⇒ AVL 继承自 BST。

转载于:https://www.cnblogs.com/mtcnn/p/9423688.html

你可能感兴趣的文章
整数对题目
查看>>
php设计模式-观察者模式
查看>>
NFC技术:使用Android Beam技术传输文本(一)
查看>>
C++判断一个文件是否可以正确打开的代码
查看>>
unity 判断 是手机还是平板
查看>>
VisualStudio2015单步调试
查看>>
【进程资源】监视进程资源
查看>>
团队成员效绩评定
查看>>
【數據結構】哈工大實驗一:一元多项式(代碼以及報告)
查看>>
(转)spring boot注解 --@EnableAsync 异步调用
查看>>
简单理解Socket
查看>>
Hortonworks HDP Sandbox定制(配置)开机启动服务(组件)
查看>>
DHCP Option 60 认识
查看>>
浅析连续子向量,子数组和(一维,二维)问题
查看>>
C/C++中各种类型int、long、double、char表示范围(最大最小值)
查看>>
Linux环境下Eclipse + Tomcat + MySQL 配置J2EE开发环境的方法
查看>>
机器学习实战:第九章 树回归
查看>>
while(~scanf("%d %d",&a,&b))和while(scanf("%d %d",&a,&b)!=EOF)
查看>>
使用vs code开发纸壳CMS并启用Razor智能提示
查看>>
动态投资回收期Pt小于计算期n
查看>>