二叉查找树的平衡(DSW算法)

树适合于表示某些领域的层次结构(比如Linux的文件目录结构),使用树进行查找比使用链表快的多,理想情况下树的查找复杂度O(log(N)),而链表为O(N),但理想情况指的是什么情况呢?一般指树是完全平衡的时候。哪最坏的情况是什么呢?就是树退化为链表的时,这时候查找的复杂度与链表相同。就失去了树结构的意义。所以树的平衡是非常重要的,这一节我们主要讨论树的平衡问题。

image


如果树中任一节点的两个子树的高度差为0或者1,该二叉树就是高度平衡的。 上图中,A是平衡二叉搜索树,B是不平衡的,C直接退化为链表了。

为保持树的平衡,有两种策略,一种是全局的,即当插入和删除操作完毕后,对树进行重建,全局调整树为平衡树;另一种是局部调整,即当插入或者删除导致树不平衡时就立即在局部范围内调整,使树保持平衡,这个是后面要讨论的AVL树。下面我们先讨论一下全局调整的方法。

有序数组创建二叉查找树

要想实现树的平衡,最简单的想法是我们可以设想一下将树的所有节点从小到大排序后,将中间值作为根节点,左侧的值作为左子树,右侧的所有值作为右子树,每个子树再按根节点的划分方法,以此类推,代码表示如下:

// data是排序后的数组 template<class T> void BST<T>::balance (T data[], int first, int last) { if (first <= last) { int middle = (first + last)/2; //父节点,这种方法相当于一层一层的构造下一层子节点的父节点 insert(data[middle]); balance(data,first,middle-1); //左子树再递归调用继续构造 balance(data,middle+1,last); //右子树再递归调用继续构造 } }

哪怎么得到有序数组呢?直接用排序算法排序?在二叉查找树中,这种方法比较笨,可以利用二叉查找树的性质,中序遍历得到有序序列。可以先对树做中序遍历,得到排序数组,再用balance进行平衡。

为什么二叉查找树中序遍历得到有序序列呢?这和二叉查找树的定义有关,对于二叉查找树中的一个节点,其左子树的值小于该节点,其右子树的值大于该节点。而中序遍历是:左->中->右,这个顺序,刚好是从小到大的顺序。比如上图中的A、B、C三颗二叉查找树,只要是数据相同的二叉查找树,不管怎么排列,中序遍历的结果都是相同的{10,15,20,23,25,30}。

这种办法是比较笨的办法,代价比较大,等于是完全重新建立二叉查找树,有没有聪明一点的方法呢?下面DSW算法就是比较聪明的办法。

DSW算法(Day–Stout–Warren algorithm)

主要思路:

先将任意的二叉查找树转化为类似于链表的树,成为主链或主干(backbone or vine);

围绕主链中第二个节点的父节点,反复将其旋转,将这棵被拉伸的树在一系列步骤中转化为完全平衡的树;

第一阶段:右旋转形成主链

其中涉及旋转(左旋转、右旋转)的操作,我们先看一下右旋转的逻辑,左旋转与右旋转对称,伪代码如下:

/************************************************************************ * 子节点Ch围绕父节点Par的右旋转 * Before After * Gr Gr * \ \ * Par Ch * / \ / \ * Ch Z X Par * / \ / \ * X Y Y Z ***********************************************************************/ rotateRight(Gr, Par, Ch) if Par不是树的根节点 //即Gr节点存在 将Ch转作为Gr的右子节点(即,Gr作为Ch的父节点) Ch的右子树转作为Par的左子树 节点Ch将Par作为右子节点

接下来开始DSW算法的第一阶段:创建主链:伪代码如下:

// 创建主链,采用右旋转,将所有的左子树都旋转到主链上,最后形成一条右子树(单链形式) createBackbone(root) tmp = root; while (tmp != 0) if tmp有左子节点 围绕tmp旋转该子节点; //该左子节点将成为tmp的父节点 tmp设置为刚刚成为父节点的子节点; else 将tmp设置为它的右子节点;

其过程如下图所示:

二叉查找树的平衡(DSW算法)


可以看到,右旋的过程就是不断把左子树旋转到主链的过程。

第二阶段:左旋转转换为平衡树

右旋转形成主链后,下个阶段需要左旋转,我们看一下左旋转,分析思路与右旋转相同,下图中节点D围绕节点B左旋转,

image

/************************************************************************ * 子节点Ch围绕父节点Par的左旋转 * Before After * Gr Gr * \ \ * Par(B) Ch(D) * / \ / \ * A Ch(D) Par(B) E * / \ / \ * C E A C ***********************************************************************/ rotateLeft(Gr, Par, Ch) if Par不是树的根节点 //即Gr节点存在 将Ch转作为Gr的右子节点(即,Gr作为Ch的父节点) Ch的左子树转作为Par的右子树 节点Ch将Par作为左子节点

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wssjfy.html