平衡二叉树可视化算法.doc

摘要：二叉树是一种重要的数据结构，树结点按照一定关系存储而构成的二叉查找树因其搜索效率很高而被广泛应用。但二叉树的实现主要是基于二叉链表形式在内存中进行数据组织，对于各结点间的父子关系不方便观察。因此本文提出一种算法以最大的绘图空间利用率对二叉树进行可视化实现，对于程序调试时的结点关系查看和教学演示都有很好的实用价值。
1. 引言
二叉查找树是一种数据结构，它支持多种动态集合操作，在二叉查找树上执行的基本操作与树的高度成正比。对于一棵含n个结点的完全二叉树这些操作的最坏情况运行时间为O(log2n)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况运行时间为Θ(n)。
对二叉查找树进行一些变形，可以避免二叉查找树的严重不平衡现象，如平衡二叉树、红黑树等。
上述数据结构一般以二叉链表的形式进行实现，数据主要存储在内存中以便搜索。但是对于某些有限制条件的二叉树（如红黑树）来说，在程序实现后的调试过程中，如果没有一个可视化的显示方法，要确定所建立的树结构是否满足所有限制条件是很不方便的。此外，对于数据结构的教学过程中，如果能够以图形化的方式来表示结构的建立过程，则更加直观易懂。
因此，实现二叉树的可视化具有重要意义。参考文献[1]实现了一种二叉树的可视化算法，但该算法是基于完全二叉树的结构进行结点布局的，当某些子树缺失时，这种表示方法对空间浪费较大。
本文实现了一种更有效的算法，可以在有限的平面绘图空间内绘制更多的结点，让结点排列更紧凑。
2. 二叉查找树基本结构描述
最简单的二叉查找树结点结构如下，
struct node {
int key; /*关键字域*/
struct node *parent; /*指向父节点指针*/
struct node *left; /*指向左子结点指针*/
struct node *right; /*指向右子结点指针*/
}
如上结点结构所构成的二叉查找树不能避免树的不平衡问题，在结点中增加数据域并定义一些平衡化处理方法后可以保证二叉查找树总是会处于一种平衡的或近乎平衡的状态，其中红黑树就是一种近乎平衡的二叉查找树。红黑树的结点结构中增加了一个结点颜色域(color)，其结构如下，
struct node {
int key; /*关键字域*/
color_type color; /*结点颜色，非红即黑*/
struct node *parent; /*指向父节点指针*/
struct node *left; /*指向左子结点指针*/
struct node *right; /*指向右子结点指针*/
}
红黑树需要保证以下红黑性质：（1）每个结点是红的，或者是黑的。（2）根结点是黑的。（3）每个叶节点是黑的。（4）如果一个结点是红的，则它的两个子结点是黑的。（5）对每个结点，从该节点到其子孙结点的所有路径上包含相同数目的黑结点。
为了满足以上性质，红黑树定义了额外的“旋转”操作，即左旋操作和右旋操作，当树结构不满足如上的红黑性质时，通过旋转操作可保持红黑树的近乎平衡性，而平衡二叉树（AVL）同样是基于这两种额外操作来保持树的平衡的。
由于红黑树应用广泛，且操作相对复杂，其操作集合是另外两种二叉树的超级，所以本文针对红黑树实现其可视化算法。为了树的可视化实现，在红黑树种增加几个数据域，形成如下的结点结构，
struct node {
int key; /*关键字域*/
color_type color; /*结点颜色，非红即黑*/
int left_offset; /*该结点距其左子树根结点的单位水平距离数*/
int right_offset; /*该结点距其右子树根结点的单位水平距离数*/
int total_left_offset; /*该结点距其左子树最左结点的单位水平距离数*/
int total_right_offset; /*该结点距其右子树最右结点的单位水平距离数*/
struct node *parent; /*指向父节点指针*/
struct node *left; /*指向左子结点指针*/
struct node *right; /*指向右子结点指针*/
}
由上述结构可知主要增加了四个水平距离域。现定义水平距离如下：一个单位的水平距离等于叶节点与其父节点的连线在水平方向的投影距离，如图（1）中的距离d为一个单位的水平距离。

图（1） 水平距离定义
另外，为了处理代码中的边界条件，在红黑树中增加了一个哨兵结点，在此不妨设其名称为nil，所有结点如果没有左、右子树，则相应left、right域均指向该nil结点。在绘图时，nil结点不必绘制。
3. 二叉树可视化算法描述
3.1 算法基本原理
本算法的目的是使某一子树的根结点与其父节点的分支连线在水平方向的投影距离最小，为了说明算法的原理，采用以下两步进行阐述。
（1） 当结点是叶节点时，其left、right域指向nil结点，则叶节点到其左右子树的根结点的最短水平距离各为1，如图（2）所示。
1

图（2） 叶结点offset域
（2） 当结点A是非叶子结点时，A到其左（右）子树的根结点B的最短水平距离等于B到该子树的最右（左）nil结点间的水平距离。此时B的最右（左）nil结点与A在同一条垂直线上。而假设B有右子树，其根结点为C，则B到其最右nil结点的距离等于C到其最左nil结点与C到其最右nil结点的距离和。如图（3）所示。
C->total_right_offset
C->total_left_offset
B->total_right_offset
A->left_offset

图（3） 非叶结点offset域
到此为止，可以给出新增加的四个offset域的定义式：
nil->total_left_offset = nil->total_right_offset = 1……….(1)
nil->right_offset = nil->left_offset = 0……….(2)
x->right_offset = x->right->total_left_offset……….(3)
x->left_offset = x->left->total_right_offset……….(4)
x->total_right_offset = x->right->total_left_offset + x->right->total_right_offset
……….(5)
x->total_left_offset = x->left->total_left_offset + x->left->total_right_offset
……….(6)
其中结点x为非哨兵（nil）结点。
改变二叉树结构的操作过程（插入和删除）最终都转换到了对叶节点的操作，而由（1）~（6）式可看出一个结点的左（右）offset域其实是由其左（右）子树所包含的叶节点个数决定的，因此，可以设计算法在增加或删除了一个叶节点后再由此到根结点上溯进行各相关结点offset域的更新。
3.2 算法实现
针对红黑树的操作中涉及到叶节点数量变化的主要是插入和删除操作，在这两种操作中包含了一个辅助的旋转操作过程，因此，主要分析在上述三种操作时各offset域的变化。
3.2.1 红黑树结点的插入操作
假设在红黑树中新插入的x叶结点成为了父结点px的右子结点（左子结点情况原理相同），则根据上述公式可知父结点的total_right_offset域增加了1，其他offset域均无变化。此后令x=px，而假设x为仍其父结点px的右子结点，则px的total_right_offset域同样会增加1，total_right_offset域增加1的更新会一直沿着树上升直到x不再为px的右子结点或x为根结点。当x为根结点时，更新结束，而当x为px的左子结点时，则首先需要更新px->left_offset=px->left_offset+1=x->total_right_offset+x->total_left_offset。然后需要更新的则是px结点的total_left_offset，同理，该更新会一直沿着树上升，当x不再是px的左子结点时，循环回到开始的情况。当循环结束时，便更新了因插入而影响到的所有结点的offset域。其更新操作流程如图（4）。

图（4） 插入结点后更新offset域流程
3.2.1 红黑树的结点删除操作
由红黑树的删除算法可知，其结点的删除操作最终真正删除的是一个叶结点，叶结点的删除会导致其父结点的total_right_offset域或total_left_offset域的值减1，此变化会一直沿着树上升直到根结点，其原理和插入操作的结点offset域更新相同，在此不再赘述。
3.2.3 红黑树的旋转操作
旋转分为左旋和右旋两种，在此只分析左旋操作对各offset域的影响，右旋操作原理相同。
如图（5）a为左旋之前子树结构，b为左旋之后子树结构，由图不难看出，旋转前后A的左子树α和B的右子树β的相对于父结点位置没有变化，故A->total_left_offset和A->left_offset以及B->total_right_offset和B->right_offset不变。对于其他offset域，由上述公式，左旋之前，有：
A->right_offset=B->total_left_offset
=β->total_right_offset+β->total_left_offset
A->total_right_offset=B->total_right_offset+B->total_left_offset
=β->total_right_offset+β->total_left_offset
+γ->total_right_offset+γ->total_left_offset
B->left_offset=β->total_right_offset
B->total_left_offset=β->total_right_offset+β->total_left_offset
旋转之后，有：
A->right_offset=β->total_left_offset
A->total_right_offset=β->total_right_offset+β->total_left_offset
B->left_offset=A->total_right_offset
=β->total_right_offset+β->total_left_offset
B->total_left_offset= A->total_right_offset+A->total_left_offset
=α->total_right_offset+α->total_left_offset
+β->total_right_offset+β->total_left_offset
而对于该子树的父结点C，假设旋转前A是C的右子树（左子树分析同理），则旋转不会改变C的有关左子树的offset域。对于右子树的相关域，在旋转前有：
C->right_offset=A->total_left_offset
=α->total_right_offset+α->total_left_offset
C->total_right_offset=A->total_left_offset+A->total_right_offset
=α->total_right_offset+α->total_left_offset
+β->total_right_offset+β->total_left_offset
+γ->total_right_offset+γ->total_left_offset
旋转后，有：
C->right_offset=B->total_left_offset
=α->total_right_offset+α->total_left_offset
+β->total_right_offset+β->total_left_offset
C->total_right_offset=B->total_left_offset+B->total_right_offset
=α->total_right_offset+α->total_left_offset
+β->total_right_offset+β->total_left_offset
+γ->total_right_offset+γ->total_left_offset
可见旋转之后C的只是right_offset域有改变，total_right_offset域没有变化，结合公式（1）~（6）易知该变化不会沿着C结点向上传递。

a b
图（5） 左旋操作
结合上述分析，可以很容易地将上述公式实现在旋转操作的代码后面从而实现相关offset域的调整。
3.3 算法时间效率分析
由上述对于算法的描述可知，对于结点offset域的更新操作需要沿叶结点到根的一遍上溯，已知一棵有n个内结点的红黑树的高度至多为2log2(n+1)，则该上溯过程的操作时间为O(log2n)，与插入操作的时间复杂度相同，如果需要旋转操作，则需要O(log2n)+O(1)的操作，因此加入对offset的更新操作后红黑树的插入和删除操作的时间复杂度仍为O(log2n)。
4. 可视化算法实现结果及与现有算法对比
如图（6）为使用完全二叉树的绘图方法绘制的红黑树，可以看出对于该绘制方法，存在着大量的空白结点空间未被利用。

图（6） 按照完全二叉树进行结点绘制
图（7）为本算法实现后的绘制结果，对比传统方法可以看出，在左右子树均不越过通过父结点的垂线的情况下，该算法对水平空间进行了最大化的利用（其中nil结点并未绘制）。

图（7） 本算法的绘制结果
5. 结论
通过对平衡二叉树基本操作的分析，本文提出了一种可视化算法，即在二叉树结点结构中增加四个偏移域，并给出了更新操作流程，从而对二叉树的一种更紧凑的可视化方法进行了实现，并进行了程序验证。结果表明，该算法具有较好的执行效率，并且能够在有限的空间内绘制更多的二叉树结点，是实现二叉树可视化的一种较好方案。
参考文献：