低调整率的广义AVL树及其统一重平衡方法
现有绝大部分数据结构技术都是串行数据结构技术。随着多核处理器的普及，如何在并发环境下高效地实现这些技术显得十分重要[1]。其中有序词典数据结构获得较多的研究[2]，主要包括跳跃表和维持对数高度的平衡二叉搜索树。由于不需要对结构进行经常性的调整，跳跃表已经成为应用最广泛的并发词典技术[1-9]。最近，研究人员还开发出了具有良好并发性能的红黑树[2]、AVL（AdelsonVelskii and Landis树[3]和伸展树[4]。早期的并发AVL树是通过解耦更新操作和重平衡操作来实现的[5]，更新操作时不进行调整，但记录下平衡约束的破坏情况，当可以进行调整时，恢复所有的平衡约束；近几年，软件事务性内存技术用于AVL树[3]、红黑树[2]和伸展树[4]获得了良好的效果；国内学者通过对副本节点进行操作而数据节点保持不变，开发了一种无锁并发链表算法[6]，基于节点重用策略进行了无锁并发技术在二叉搜索树中研究[7]。
所有这些研究都是基于经典串行数据结构，通过增加一些新方法或新技术使之适应并发应用。要使经典数据结构能更好地适用于并发应用，不能仅局限于实现环节，还可对它们进行改造，但这方面的研究报告/论文很少。适合于并发应用的数据结构一般有以下两大特点或之一：1在更新操作过程中较少地对原有结构进行调整；2调整具有局域性。本文提出的广义AVL树具有非常低的调整率，已经可以达到万次更新操作只需一次重平衡操作的程度；尽管调整时其局域性略差，但平摊到单次操作，其影响的节点还是非常少的。
1AVL树的统一重平衡方法
当AVL树的左右子树树高相差超过1时，就需要调整以使树重归于平衡。重平衡调整分4种情况进行旋转：左旋、右旋、左旋再右旋、右旋再左旋。这种分类重平衡的方法非常有效，红黑树和AA树（Arne Andersson tree的双红和双黑调整也是这么处理的。但该方法也有两个缺点
1实现调整算法时，代码量大且流程繁杂，因此容易出错且调试困难；2该方法没有通用性，对于如左右子树高度相差超过2的强失衡的情况，采用分类重平衡方法将导致太多的分类情况，这将极大地增加理解和编程的复杂度，因此该方法不适合处理强失衡的情况。
AVL树的失衡节点左右子树高度相差2，因此只需向失衡节点更深的子树方向进行搜素，一定可以得到一个子节点和一个孙节点。把这三个节点及其四棵子树按完全二叉树的方式进行重排，即可使失衡的节点重新回归平衡，如图1所示。这7个节点可以叫“3+4”节点，清华大学邓俊辉提出的“3+4”重构方法就是这样的重平衡方法[10]，但该方法仍然采用分类方法实现。类似的调整方法在文献[11]中叫填空法、在文献[12]中叫选择调整法。
图片
图1AVL树重平衡的4种情况
本文提出的统一重平衡方法，采用自动计算分类的形式，对“3+4”节点进行调整，该方法流程简洁且代码量小。用有8个指针的节点指针数组p[8]收集“3+4”节点信息，如图1所示。图1中的数字为节点编号，1号节点为失衡节点，用p[1]存储；2号节点为1号节点较深的子节点，用p[2]存储；5号节点为1号节点较浅的子节点，用p[5]保存，其他依此类推，并用p[0]存储失衡节点的父节点指针。重平衡后，为了方便重构二叉树，将重平衡后的结果（节点编号按完全二叉树的层序进行存储。需要重平衡的情况有4种，可以用二维数组tb[4][8]来存储，具体数据为：{ {0，2，3，1，4，7，6，5}， {0，3，2，1，6，4，7，5}， {0，3，1，2，5，4，7，6}， {0，2，1，3，5，6，4，7} }。重构时，从二维数组提取分类数据，如分类情况1的数据为idx[]={0，3，2，1，6，4，7，5}，其中，“1”是第3个数据，“7”是第6个数据（6=2*3，“5”是第7个数据（7=2*3+1；这意味p[1]的左子树是p[7]、p[1]的右子树是p[5]，其他依此类推。不难发现，重构可以这样进行，p[ idx[i] ]的左子树是p[ idx[2*i] ]、右子树是p[ idx[2*i+1] ]。计算分类情况可以采用Huffman编码的方式，向更深的子树搜索时向左编码0、向右编码1，如图1各子图左半部分所示。按完全二叉树重排后的二叉树如图1各子图右半部分所示。
算法1AVL树的统一重平衡算法。
有序号的程序——————————Shift+Alt+Y
程序前
输入：失衡节点、失衡节点的父节点。
输出：调整前后的高度改变信息。
1
保留失衡节点的高度
2
计算分类号kase（初值为0及收集“3+4”节点信息
a p[1]=失衡节点
b for i=1 to 2
如果p[i]的左子树更深
p[i+1]=p[i]的左子树
p[i+4]=p[i]的右子树