二叉树平衡（DSW算法）

柔情只为你懂 2023-02-22 10:46 26阅读 0赞

## 一、前言 ##

[《二叉查找树全面详细介绍》][Link 1]中讲解了二叉树操作：搜索（查找）、遍历、插入、删除。[《二叉树遍历详解（递归遍历、非递归栈遍历，Morris遍历）》][Morris]详细讲解了二叉树遍历的几种方法。[《二叉树平衡（有序数组创建）》][Link 2]通过了一种构建平衡二叉树的方法

[《二叉树平衡（有序数组创建）》][Link 2]讨论的算法的效率有点低，因为在创建完全平衡的树之前，需要使用一个额外的有序数组。为了避免排序，这一算法需要破坏树并用中序遍历把元素放在数组中，然后重建该树，这样做效率并不高，除非树很小。然而，存在几乎不需要存储中间变量也不需要排序过程的算法。Colin Day提出了非常简洁的DSW算法，Quentin F. Stout以及Bette L. Waren 对此算法进行了改进，本文讲解DSW算法构建平衡二叉树（完全平衡二叉树）。

## 二、知识点回顾 ##

### 2.1 二叉树的旋转 ###

有两种旋转方法：

（1）左旋转：将根节点旋转到（根节点的）右孩子的左孩子位置

（2）右旋转：将根节点旋转到（根节点的）左孩子的右孩子位置

下图为左、右旋转图，黄色节点为旋转的根节点，灰色节点是可以有也可以没有的节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

## 三、DSW算法（Day–Stout–Warren algorithm） ##

一般来说，DSW算法首先将任意的二叉查找树转换为类似于链表的树，称为主链或主干。然后围绕主链中第二个节点的父节点，反复将其旋转，将这棵被拉伸的树在系列步骤中转换成完全平衡的树。DSW算法可以分为两个大的步骤。

步骤一：将二叉树右旋转形成主链；

步骤二：左旋转转换为平衡树；

其中步骤二可以分为两个阶段：

阶段一：左旋n-m次

阶段二：进入循环根据每一层节点数进行旋转。

### 3.1 步骤一 ###

createBackbone (root)
        tmp = root;
        while (tmp !=0)
            if tmp有左子节点
            	围绕tmp旋转该子节点: //这样该左子节点将成为tmp的父节点
        	tmp设置为刚刚成为父节点的子节点;
         else 将tmp设置为它的右子节点:

步骤一实例演示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

###  ###

### 3.2 步骤二 ###

createPerfectTree ()
        n=节点数;
        m = (1 << (int)log2(n)) - 1; //计算当前节点数n与最接近完全平衡二叉树中节点数之间的差，多出的节点将单独处理
        // 第一阶段：进行左旋m-n次
        
        // 第二阶段：进入循环根据每一层节点数进行左旋转
        while (m> 1)
            m=m/2;
            从主链的顶部开始做m次旋转;

这里不要好理解的是，这两个阶段都是进行左旋转，为什么要分开进行？

个人理解：第一阶段需要先进行n-m次左旋转，是为了保证最后一排阶段是在树的最左侧。第二阶段，可以理解为根据树的层次中节点数量进行旋转次数。有点抽象不容易理解，看图，更直观些，容易加深理解。

1）第一阶段第一次旋转，对节点1进行向左旋转

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2][]

2）第一阶段第二次旋转，旋转节点是上一次旋转节点的后面第2个节点也就是节点3作为本次旋转节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3][]

3）第一阶段的两次旋转完成

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4][]

4）第二阶段第一层第一次旋转，以第一阶段旋转完的树根节点作为本次旋转节点。

第一层旋转次数3次， 3 = 7>>1。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5][]

5）第二阶段第一层第二次旋转，旋转节点是上一次旋转节点的后面第2个节点也就是节点5作为本次旋转节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6][]

6）第二阶段第一层第三次旋转，旋转节点是上一次旋转节点的后面第2个节点也就是节点8作为本次旋转节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 7][]

7）第二阶段第一层第三次旋转完成。我们发现，当前生成的树是平衡二叉树，但不是完全平衡二叉树，其中有两个节点是在最后一层的右边。最后一层节点数量和步骤一中旋转次数是对应的。现在需要将其转换成完平衡二叉树，需要继续旋转。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 8][]

8）第二阶段第二层第一次旋转，以上一层旋转完的树根节点作为本次旋转节点。

第二层旋转次数1次， 1 = 3>>1。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 9][]

9）旋转完成，完全平衡二叉树构建成功。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 10][]

## 四、总结 ##

整体来说这种思路有些抽象，需要结合图多多领悟。时间复杂度和空间复杂度相比《二叉树平衡（有序数组创建）》好很多。

## 五、编码实现 ##

//==========================================================================
    /**
    * @file    : DswBST.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107095634
    * @author  : niebingyu
    * @title   : DSW算法构建平衡二叉树
    * @purpose : DSW算法构建平衡二叉树
    */
    //==========================================================================
    #pragma once
    #include "GenBST.h"
    
    template<class T>
    class DswBST : private BST<T> 
    {
    public:
        DswBST(T* a, int len);    //根据数组中的数据构造树，调试测试用
    
        // 平衡二叉树
        void dswBalance();
    
        // 前序遍历二叉树
        void preorder(){ BST<T>::preorder(); }
    
        // 中序遍历二叉树
    	void inorder() { BST<T>::inorder(); }
    
    protected:
        // 步骤一：将二叉树右旋转形成主链
        void createBackbone();
        // 步骤二：左旋转转换为平衡树
        void creatPerfectTree();
    
        // 右旋转
        void rotateRight(BSTNode<T>* Gr, BSTNode<T>* Par, BSTNode<T>* Ch);
    
        // 左旋转
        void rotateLeft(BSTNode<T>* Gr, BSTNode<T>* Par, BSTNode<T>* Ch);
    
    private:
        int m_count;
    };
    
    template<class T>
    DswBST<T>::DswBST(T* a, int len) 
    {
    	m_count = 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 <-tmp       25 <-tmp         23               23
    *       /  \             /  \           /  \               \                \
    *     23    28          25   40        23   30              25              25
    *                      /  \                /  \              \                \
    *                     23   28             28   40            30 <-tmp         28
    *                                                           /  \               \
    *                                                          28  40               30
    *                                                                                \
    *                                                                                 40 <-tmp
    ***********************************************************************************************/
    // 步骤一：将二叉树右旋转形成主链
    template<class T>
    void DswBST<T>::createBackbone() 
    {
        BSTNode<T>* Gr = 0, *Par = this->m_root, *Ch = 0;
        while (Par != 0) 
        {
            Ch = Par->m_left;
            if (Ch != 0) 
            {
                rotateRight(Gr, Par, Ch);
                Par = Ch;
            }
            else 
            {
                Gr = Par;
                Par = Par->m_right;
            }
    
            // 旋转过程中，如果是绕根节点的右节点旋转时要将根节点置为原根节点的右节点
            if (Gr == 0)
                this->m_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(BSTNode<T>* Gr, BSTNode<T>* Par, BSTNode<T>* Ch) 
    {
        if (Gr != 0)
            Gr->m_right = Ch;
    
        Par->m_left = Ch->m_right;
        Ch->m_right = Par;
    }
    
    // 左旋转
    template<class T>
    void DswBST<T>::rotateLeft(BSTNode<T>* Gr, BSTNode<T>* Par, BSTNode<T>* Ch) 
    {
        if (Gr != 0)
            Gr->m_right = Ch;
    
        Par->m_right = Ch->m_left;
        Ch->m_left = Par;
    }
    
    // 步骤二：左旋转转换为平衡树
    template<class T>
    void DswBST<T>::creatPerfectTree() 
    {
        int n = m_count;
        if (n < 3)
            return; //节点数目小于3不用平衡
    
        int m = (1 << (int)log2(n)) - 1;
        BSTNode<T>* Gr = 0;
        BSTNode<T>* Par = this->m_root;
        BSTNode<T>* Ch = this->m_root->m_right;
    
        this->m_root = this->m_root->m_right; //修改root指针
        // 第一阶段： 左旋n-m次
        for (int i = 0; i < n - m; i++) 
        {
            rotateLeft(Gr, Par, Ch);
            Gr = Ch;
            Par = Gr->m_right;
            if (0 != Par) 
                Ch = Par->m_right;
            else 
                break;
        }
    
        // 第二阶段，进入while循环
        while (m > 1) 
        {
            m = m >> 1;
            BSTNode<T>* Gr = 0;
            BSTNode<T>* Par = this->m_root;
            BSTNode<T>* Ch = this->m_root->m_right;
    
            this->m_root = this->m_root->m_right;
            for (int i = 0; i < m; i++) 
            {
                rotateLeft(Gr, Par, Ch);
                Gr = Ch;
                Par = Gr->m_right;
                if (0 != Par) 
                    Ch = Par->m_right;
                else 
                    break;
            }
        }
    }

**测试代码**

//==========================================================================
    /**
    * @file    : DswBSTTest.h
    * @blogs   : 
    * @author  : niebingyu
    * @title   : 测试DSW算法构建平衡二叉树
    * @purpose : 测试DSW算法构建平衡二叉树
    *
    */
    //==========================================================================
    #pragma once
    #include "DswBST.h"
    using namespace std;
    
    #define NAMESPACE_DSWBSTTEST namespace NAME_DSWBSTTEST {
    #define NAMESPACE_DSWBSTTESTEND }
    NAMESPACE_DSWBSTTEST
    
    // 测试用例
    void Test1()
    {
        vector<int> data = { 1,2,3,4,5,6,7,8,9};
        DswBST<int> tree(data.data(), data.size());
        tree.dswBalance();
    
        cout << "Test1 前序遍历: ";
        tree.preorder();
        cout << "\nTest1 中序遍历: ";
        tree.inorder();
        cout << endl;
    }
    
    void Test2()
    {
        vector<int> data = { 5, 10, 20, 15, 30, 25, 40, 23, 28 };
        DswBST<int> tree(data.data(), data.size());
        tree.dswBalance();
    
        cout << "Test2 前序遍历: ";
        tree.preorder();
        cout << "\nTest2 中序遍历: ";
        tree.inorder();
        cout << endl;
    }
    
    // 测试用例
    void Test3()
    {
        vector<int> data;
        for (int i = 1; i <= 33; ++i)
            data.push_back(i);
    
        DswBST<int> tree(data.data(), data.size());
        tree.dswBalance();
    
        cout << "Test1 前序遍历: ";
        tree.preorder();
        cout << "\nTest1 中序遍历: ";
        tree.inorder();
        cout << endl;
    }
    NAMESPACE_DSWBSTTESTEND
    
    void DswBSTTest_Test()
    {
        NAME_DSWBSTTEST::Test1();
        NAME_DSWBSTTEST::Test2();
        NAME_DSWBSTTEST::Test3();
    }

**执行结果：**

![20200702233918920.png][]

[Link 1]: https://blog.csdn.net/nie2314550441/article/details/107030025
[Morris]: https://blog.csdn.net/nie2314550441/article/details/107073598
[Link 2]: https://blog.csdn.net/nie2314550441/article/details/107092408
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200702232837625.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200702233001231.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200702233109399.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200702233136381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200702233157143.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200702233233709.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200702233257679.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200702233322881.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200702233341691.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200702233428642.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200702233449809.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200702233918920.png]: https://img-blog.csdnimg.cn/20200702233918920.png