二叉查找树的平衡（DSW）_平衡二叉树的查找方法

作者：运维做开发 | 2024-06-28 15:03:06

踩

平衡二叉树的查找方法

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

如果树中任一节点的两个子树的高度差为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);    //右子树再递归调用继续构造
    }
}
1
2
3
4
5
6
7
8
9
10

哪怎么得到有序数组呢？直接用排序算法排序？在二叉查找树中，这种方法比较笨，可以利用二叉查找树的性质，中序遍历得到有序序列。可以先对树做中序遍历，得到排序数组，再用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作为右子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

// 创建主链，采用右旋转，将所有的左子树都旋转到主链上，最后形成一条右子树（单链形式）
createBackbone(root)
    tmp = root;
    while (tmp != 0) 
        if tmp有左子节点
            围绕tmp旋转该子节点；    //该左子节点将成为tmp的父节点
            tmp设置为刚刚成为父节点的子节点；
        else 
            将tmp设置为它的右子节点；
1
2
3
4
5
6
7
8
9

其过程如下图所示：

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

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

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

/************************************************************************
 *  子节点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作为左子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

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

过程如下图所示：

最开始，左旋转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 <-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() {
	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->root = this->root->right; //修改root指针
    // 第一阶段： 左旋n-m次
	for(int i = 0; i < n - m; i++) {
		rotateLeft(Gr, Par, Ch);
        Gr = Ch;
        Par = Gr->right;
        if (0 != Par) {
            Ch = Par->right;
        } else {
            break;
        }
	}

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

        this->root = this->root->right;	
        for(int i = 0; i < m; i++) {
            rotateLeft(Gr, Par, Ch);
            Gr = Ch;
            Par = Gr->right;
            if (0 != Par) {
                Ch = Par->right;
            } else {
                break;
            }
        }
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/766350