WAVL 树

WAVL 树(Weak AVL Tree,弱 AVL 树)是一种自平衡二叉搜索树,由哈普林、塞克斯顿与塔扬提出。它用整数秩来度量节点高度,规定每个节点与其父节点之间的秩差只能取一或二,从而在 AVL 树与红黑树之间取得平衡。

概述

传统 AVL 树要求兄弟子树高度差不超过一,平衡严格但删除时旋转可能较多;红黑树约束较松,树可能更高。WAVL 树引入秩差规则,使得只经历插入的树等价于 AVL 树,而经历删除后的树高度上界与红黑树相当,同时删除操作的重平衡旋转次数被严格限制在常数。

核心特点

• 每个节点维护一个非负整数秩,叶子的秩为零。
• 任意节点到其孩子的秩差必须是一或二,外部空节点秩为负一。
• 插入通过升秩与至多两次旋转恢复平衡,行为与 AVL 树一致。
• 删除通过降秩传播,最终至多一次旋转即可修复,避免了红黑树删除时的多次调整链。
• 树高上界约为以二为底的对数的两倍,优于纯红黑树的常见界。

应用场景

WAVL 树适合插入和删除都频繁、又希望树保持较低高度的有序集合与字典实现。它在数据库索引、内存有序表以及需要可预测重平衡代价的系统中有潜在价值,尤其当删除操作占比较高时,其旋转次数上界的保证很有吸引力。

常见问题

问:WAVL 树为什么叫弱 AVL 树?答:因为它弱化了 AVL 树秩差必须为一的严格条件,允许秩差为二,从而在删除后依然能维持较优高度,却不必付出频繁旋转的代价。

问:它与红黑树是等价的吗?答:两者高度上界接近且都可用秩来描述,但 WAVL 树的秩规则不同,纯插入时它等同 AVL 树,删除旋转次数也有更强的常数上界。