怎样一次性统一行高(低调整率的广义AVL树及其统一重平衡方法)
最近，研究人员开发了红黑树[2]，AVL树[3]和伸展树[4]，并发性很好。早期的并发AVL树是通过解耦更新操作和重新平衡操作实现的[5]。在更新操作期间没有进行任何调整，但是记录了平衡约束的破坏。当调整成为可能时，所有的平衡约束都恢复了。
所有这些研究都基于经典的串行数据结构，并通过添加一些新的方法或技术来适应并发应用。为了使经典的数据结构更好地适用于并发应用程序，它们不仅应该局限于实现链接，还应该由对修改。然而，在这方面的研究报告很少。适用于并发应用的数据结构一般有以下两个特征或其中之一：1 .在更新操作期间，对的原始结构调整较少；2调整是局部的。本文提出的广义AVL树具有很低的调整率，可以达到一万次更新操作只需要一次再平衡操作的水平；尽管它的局部性在调整过程中稍差，但它影响的节点很少，即使它扩展到单个操作。1AVL树的统一再平衡方法
当AVL树的左右子树的高度差超过1时，需要调整以使树恢复平衡。重新平衡调整可以在四种情况下旋转：左手，右手，左手和右手，右手和左手。这种分类再平衡的方法非常有效，红黑树和AA树(Arne Andersson树)的双红双黑调整也是这样处理的。然而，这种方法也有两个缺点：1。在实现调整算法时，代码量大，过程复杂，容易脱离错，调试困难；这种方法是不通用的，对是在很强的不平衡的情况下，如左右子树的高度差超过2。使用分类再平衡方法会导致过多的分类情况，这将大大增加理解和编程的复杂性，因此这种方法不适合处理强不平衡的情况。
AVL树的非平衡节点的左右子树的高度差为2，所以你只需要搜索非平衡节点的较深的子树就可以得到一个子节点和一个孙子节点。通过在一个完整的二叉树中重新排列这三个节点和它们的四个子树，不平衡的节点可以再次返回平衡，如如图1所示。这七个节点可以称为“3 4”节点，邓俊辉，清华大学提出的“3 4”重构方法就是这样一种再平衡方法[10]，但这种方法仍然是通过分类来实现的。类似的调整方法在文献[11]中称为填空法，在文献[12]中称为选择性调整法。画
图1 1AVL树再平衡的四种情况本文提出的统一再平衡方法采用自动计算和分类的形式，由对“34”节点进行调整。该方法流程简单，代码量少。用8个指针的节点指针数组p[8]收集“3 4”节点信息，如如图1所示。图1中的数字是节点号，1号节点是不平衡节点，由p[1]存储；2号节点是1号节点的深层子节点，由p[2]存储；5号节点是1号节点的浅子节点，由p[5]保存，其他类推，不平衡节点的父节点指针由p[0]保存。在重新平衡之后，为了方便地重建二叉树，重新平衡的结果(节点号)按照完整二叉树的顺序存储。有四种情况需要重新平衡，可以通过二维数组tb[4][8]进行存储。具体数据为：{{0，2，3，1，4，7，6，5}，{0，3，2，1，6，4，7，5}，{0，3，1，1，5}重建时，分类数据从二维数组中提取。例如，分类案例1的数据是IDX []={0，3，2，1，6，4，7，5}，其中“1”是第三个数据，“7”是第六个数据(6=2*3，“5”是第七个数据(7这意味着p[1]的左子树是p[7]，p[1]的右子树是p[5]，依此类推。不难发现，重建可以这样进行，即p[ idx[i]]的左子树是p[ idx[2*i]]，右子树是p[ idx[2*i 1]]。分类可以通过霍夫曼编码来计算。当搜索更深的子树时，代码0在左边，代码1在右边，如如图1的每个子图的左半部分所示。根据二叉树的如图1的每个子图的右半部分重新排列成完整的二叉树。
算法1 1AVL树的统一再平衡算法。序列号程序————335433543——354354354354354 shift alt y
预编程输入：不平衡节点和不平衡节点的父节点。
输出：调整前后的高度变化信息。1
保持不平衡节点2的高度
计算分类编号kase(初始值为0，收集“3 4”节点信息，p[1]=不平衡节点
如果p[i]的左子树更深，
P1的左子树=P4=P1的右子树
黑曼巴 