23°

二叉查找树的平衡(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设置为它的右子节点;

其过程如下图所示:

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

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

右旋转形成主链后,下个阶段需要左旋转,我们看一下左旋转,分析思路与右旋转相同,下图中节点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作为左子节点

通过右旋转形成主链后,开始第二阶段:主链转换为平衡树:伪代码如下:

// 需要注意的是,每次顺着主链向下操作时,每隔两个节点,都围绕其父节点进行旋转
createPerfectTree
    n = 节点数;
    m = 2^[log(n+1)]-1; //计算当前节点数n与最接近完全平衡二叉树中节点数之间的差,多出的节点将单独处理
    从主链的顶部开始做n-m次旋转;   //从主链的顶部第二个节点开始,每隔一个节点进行左旋   
    while (m > 1)   // 上面单独处理的结束,开始下面的处理
        m = m/2;
        从主链的顶部开始做m次旋转; //从主链的顶部第二个节点开始,每隔一个节点进行左旋

过程如下图所示:


最开始,左旋转2次,之后进入while循环。进入while循环后,第1轮左旋转3次,第2轮左旋转1次,然后得出平衡树。最后还是要注意,是间隔1个节点围绕其父节点进行旋转(或者说是每次从主链根节点开始,偶数节点围绕奇数节点左旋转)。可以看到,左旋转就是不断将左右子树进行平衡的过程。

DSW算法源代码

#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<list>
#include<stack>
#include<queue>
using namespace std;

//栈实现 template<class T> class Stack : public stack<T> { public: T pop() { T tmp = stack<T>::top(); stack<T>::pop(); return tmp; } };

//队列实现 template<class T> class Queue : public queue<T> { public: T dequeue() { T tmp = queue<T>::front(); queue<T>::pop(); return tmp; } void enqueue(const T& el) { queue<T>::push(el); } };

//树节点类 template<class T> class Node { public: Node():left(NULL),right(NULL){} Node(const T& e,Node<T>* l=NULL,Node<T>r=NULL):data(e),left(l),right(r){} ~Node(){} T data;
Node
left; Node* right; };

//二叉查找树的实现类 template<class T> class BST { public: BST():root(NULL),count(0){} BST(T* a, int len); //根据数组中的数据构造树,调试测试用 ~BST() { clear(); } bool isEmpty() const { return NULL == root; } void clear() { clear(root); root = NULL; } uint count; void insert(const T&); //插入 void inorder() {//深度遍历之中序树遍历 inorder(root); } void breadthFirst(); //广度优先遍历 virtual void visit(Node<T>* p) { cout << p->data << ' '; } protected: Node<T>* root; //根节点 void clear(Node<T>); void inorder(Node<T>); };

//根据数组中的内容构造树 template<class T> BST<T>::BST(T* a, int len) { root = NULL; count = 0; for (int i = 0; i < len; i++) { insert(a[i]); } }

//清除节点p及其子节点 template<class T> void BST<T>::clear(Node<T> *p) { if (p != NULL) { clear(p->left); clear(p->right); delete p; }

count = 0;

}

//插入,非递归形式 template<class T> void BST<T>::insert(const T& el) { Node<T> *p = root, *prev = NULL; while (p != NULL) { // find a place for inserting new node; prev = p; if (el < p->data) p = p->left; else p = p->right; } if (root == NULL) // tree is empty; root = new Node<T>(el); else if (el < prev->data) prev->left = new Node<T>(el); else prev->right = new Node<T>(el);

++count;

}

//广度优先遍历(从上到下,从左到右,一层一层的向下访问) template<class T> void BST<T>::breadthFirst() { Queue<Node<T>> m_queue; //要理解这里为什么要用队列,这个队列的作用是把下一层的数据放到本层数据的后面 Node<T> p = root; if (p != NULL) { m_queue.enqueue(p); while (!m_queue.empty()) { p = m_queue.dequeue(); visit(p); if (p->left != NULL) m_queue.enqueue(p->left); if (p->right != NULL) m_queue.enqueue(p->right); } } }

//中序遍历,递归实现 template<class T> void BST<T>::inorder(Node<T> *p) { if (p != NULL) { inorder(p->left); visit(p); inorder(p->right); } }

template<class T> class DswBST: public BST<T> { public: DswBST(T* a, int len); //根据数组中的数据构造树,调试测试用 void dswBalance(); protected: void createBackbone(); void creatPerfectTree(); void rotateRight(Node<T>* Gr, Node<T>* Par, Node<T>* Ch); void rotateLeft(Node<T>* Gr, Node<T>* Par, Node<T>* Ch); };

template<class T> DswBST<T>::DswBST(T* a, int len) { for (int i = 0; i < len; i++) { this->insert(a[i]); } }

template<class T> void DswBST<T>::dswBalance() { createBackbone(); creatPerfectTree(); }

// 二叉查找树转化成主链的过程分析 /**********************************************************************************************

  • 5 <-tmp 5 5 5 5
  • \ \ \ \ \
  • 10 10 10 10 10
  •  \              \               \               \               \
    
  •   20            15              15              15              15
    
  •  /  \             \               \               \               \
    
  • 15  30            20              20              20              20
    
  •     / \             \              \                \               \
    
  •    25 40            30 &lt;-tmp       25 &lt;-tmp         23               23        
    
  •   /  \             /  \           /  \               \                \
    
  • 23    28          25   40        23   30              25              25    
    
  •                  /  \                /  \              \                \
    
  •                 23   28             28   40            30 &lt;-tmp         28
    
  •                                                       /  \               \
    
  •                                                      28  40               30
    
  •                                                                            \
    
  •                                                                             40 &lt;-tmp
    

***********************************************************************************************/ template<class T> void DswBST<T>::createBackbone() { Node<T> *Gr = 0, *Par = this->root, *Ch = 0; while(Par != 0) { Ch = Par->left; if(Ch != 0) { rotateRight(Gr, Par, Ch); Par = Ch; } else { Gr = Par; Par = Par->right; } // 旋转过程中,如果是绕根节点的右节点旋转时要将根节点置为原根节点的右节点 if(Gr == 0) this->root = Ch; } }

/************************************************************************

  • 子节点Ch围绕父节点Par的右旋转
  • Before After
  • Gr Gr
  • \           \
    
  • Par         Ch
    
  • / \ / \
  • Ch Z X Par
  • / \ / \
  • X Y Y Z ********************************************************************/ template<class T> void DswBST<T>::rotateRight(Node<T> Gr, Node<T> Par, Node<T> Ch) { if(Gr != 0) Gr->right = Ch; Par->left = Ch->right; Ch->right = Par; }

template<class T> void DswBST<T>::rotateLeft(Node<T>* Gr, Node<T>* Par, Node<T>* Ch) { if(Gr != 0) Gr->right = Ch; Par->right = Ch->left; Ch->left = Par; }

template<class T> void DswBST<T>::creatPerfectTree() { int n = this->count; if (n < 3) {
return; //节点数目小于3不用平衡 } int m = (1 << ((int)(log10(n+1)/log10(2)))) - 1; Node<T> *Gr = 0; Node<T> *Par = this->root; Node<T> *Ch = this->root->right;

this-&gt;root = this-&gt;root-&gt;right; //修改root指针
// 第一阶段: 左旋n-m次
for(int i = 0; i &lt; n - m; i++) {
    rotateLeft(Gr, Par, Ch);
    Gr = Ch;
    Par = Gr-&gt;right;
    if (0 != Par) {
        Ch = Par-&gt;right;
    } else {
        break;
    }
}

// 第二阶段,进入while循环
while( m &gt; 1) {
    m = m &gt;&gt; 1;
    Node&lt;T&gt; *Gr = 0;
    Node&lt;T&gt; *Par = this-&gt;root;
    Node&lt;T&gt; *Ch = this-&gt;root-&gt;right;

    this-&gt;root = this-&gt;root-&gt;right; 
    for(int i = 0; i &lt; m; i++) {
        rotateLeft(Gr, Par, Ch);
        Gr = Ch;
        Par = Gr-&gt;right;
        if (0 != Par) {
            Ch = Par-&gt;right;
        } else {
            break;
        }
    }
}

}

int main()
{
    int a[] = { 5,10,20,15,30,25,40,23,28};
    DswBST<int> tree(a, sizeof(a) / sizeof(a[0]));
    tree.breadthFirst();
    cout << endl;
    tree.inorder();
    cout << endl;

    tree.dswBalance();
    tree.breadthFirst();
    cout << endl;
    tree.inorder();
    return 0;
}

DSW论文:One-Time Binary Search Tree Balancing:
The Day/Stout/Warren (DSW) Algorithm

本文转载自博客园,原文链接:https://www.cnblogs.com/s-lisheng/p/11974830.html

全部评论: 0

    我有话说: