博客
关于我
强烈建议你试试无所不能的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

你可能感兴趣的文章
Python模拟登入豆瓣网,并爬取小组信息
查看>>
初识Jsp,JavaBean,Servlet以及一个简单mvc模式的登录界面
查看>>
@import与link的区别与选择
查看>>
ORA-14411 该 DDL 不能与其他 DDL 并行运行处理办法
查看>>
C#筛法求出范围内的所有质数
查看>>
程序员常用的几款软件
查看>>
noi2014 起床困难综合症
查看>>
.NET ->> 分享一个字符串模糊匹配指数的方法
查看>>
HDU2907凸包+凹面
查看>>
BZOJ 1600: [Usaco2008 Oct]建造栅栏
查看>>
BZOJ 1574: [Usaco2009 Jan]地震损坏Damage
查看>>
Tiny4412 LED 程序
查看>>
电脑购买建议
查看>>
[C++]for 循环多个限制条件
查看>>
发送邮件
查看>>
Docker从入门到实战(一)
查看>>
MySql join匹配原理
查看>>
C++的高效从何而来
查看>>
吴裕雄--天生自然 HADOOP大数据分布式处理:安装XShell
查看>>
吴裕雄--天生自然 JAVASCRIPT开发学习:输出
查看>>