通过右旋转形成主链后，开始第二阶段：主链转换为平衡树：伪代码如下：
// 需要注意的是，每次顺着主链向下操作时，每隔两个节点，都围绕其父节点进行旋转 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 <-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; } } } } 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