¶þ²æ²éÕÒÊ÷µÄƽºâ£¨DSWËã·¨£©
Ê÷ÊʺÏÓÚ365ÌåÓýͶעijЩÁìÓòµÄ²ã´Î½á¹¹£¨±ÈÈçLinuxµÄÎļþĿ¼½á¹¹£©£¬Ê¹ÓÃÊ÷½øÐвéÕÒ±ÈʹÓÃÁ´±í¿ìµÄ¶à£¬ÀíÏëÇé¿öÏÂÊ÷µÄ²éÕÒ¸´ÔÓ¶ÈO(log(N))£¬¶øÁ´±íΪO(N)£¬µ«ÀíÏëÇé¿öÖ¸µÄÊÇʲôÇé¿öÄØ£¿Ò»°ãÖ¸Ê÷ÊÇÍêȫƽºâµÄʱºò¡£ÄÄ×µÄÇé¿öÊÇʲôÄØ£¿¾ÍÊÇÊ÷ÍË»¯ÎªÁ´±íµÄʱ£¬Õâʱºò²éÕҵĸ´ÔÓ¶ÈÓëÁ´±íÏàͬ¡£¾ÍʧȥÁËÊ÷½á¹¹µÄÒâÒå¡£365betÌåÓýÔÚÏßÊ÷µÄƽºâÊǷdz£ÖØÒªµÄ£¬ÕâÒ»½Ú365betÌåÓýÔÚÏßÃÇÖ÷ÒªÌÖÂÛÊ÷µÄƽºâÎÊÌâ¡£
Èç¹ûÊ÷ÖÐÈ365betÌåÓýÔÚÏß»½ÚµãµÄÁ½¸ö×ÓÊ÷µÄ¸ß¶È²îΪ0»òÕß1£¬¸Ã¶þ²æÊ÷¾ÍÊǸ߶ÈƽºâµÄ¡£ ÉÏͼÖУ¬AÊÇƽºâ¶þ²æËÑË÷Ê÷£¬BÊDz»Æ½ºâµÄ£¬CÖ±½ÓÍË»¯ÎªÁ´±íÁË¡£
Ϊ±£³ÖÊ÷µÄƽºâ£¬ÓÐÁ½ÖÖ²ßÂÔ£¬365ÌåÓýͶעÊÇÈ«¾ÖµÄ£¬¼´µ±²åÈëºÍɾ³ý²Ù×÷Íê±Ïºó£¬¶ÔÊ÷½øÐÐÖؽ¨£¬È«¾Öµ÷ÕûÊ÷ΪƽºâÊ÷£»Áí365ÌåÓýͶעÊǾֲ¿µ÷Õû£¬¼´µ±²åÈë»òÕßɾ³ýµ¼ÖÂÊ÷²»Æ½ºâʱ¾ÍÁ¢¼´ÔÚ¾Ö²¿·¶Î§ÄÚµ÷Õû£¬Ê¹Ê÷±£³Öƽºâ£¬Õâ¸öÊǺóÃæÒªÌÖÂÛµÄAVLÊ÷¡£ÏÂÃæ365betÌåÓýÔÚÏßÃÇÏÈÌÖÂÛÒ»ÏÂÈ«¾Öµ÷ÕûµÄ·½·¨¡£
ÓÐÐòÊý×é´´½¨¶þ²æ²éÕÒÊ÷
ÒªÏëʵÏÖÊ÷µÄƽºâ£¬×î¼òµ¥µÄÏë·¨ÊÇ365betÌåÓýÔÚÏßÃÇ¿ÉÒÔÉèÏëһϽ«Ê÷µÄËùÓнڵã´ÓСµ½´óÅÅÐòºó£¬½«ÖмäÖµ×÷Ϊ¸ù½Úµã£¬×ó²àµÄÖµ×÷Ϊ×ó×ÓÊ÷£¬ÓÒ²àµÄËùÓÐÖµ×÷ΪÓÒ×ÓÊ÷£¬365ÌåÓýͶע×ÓÊ÷ÔÙ°´¸ù½ÚµãµÄ»®·Ö·½·¨£¬ÒÔ´ËÀàÍÆ£¬´úÂë365ÌåÓýͶעÈçÏ£º
// 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}¡£
ÕâÖÖ°ì·¨ÊDZȽϱ¿µÄ°ì·¨£¬´ú¼Û±È½Ï´ó£¬µÈÓÚÊÇÍêÈ«ÖØн¨Á¢¶þ²æ²éÕÒÊ÷£¬ÓÐûÓдÏÃ÷Ò»µãµÄ·½·¨ÄØ£¿ÏÂÃæDSWËã·¨¾ÍÊDZȽϴÏÃ÷µÄ°ì·¨¡£
DSWËã·¨£¨Day¨CStout¨CWarren algorithm£©
Ö÷Ҫ˼·£º
- ÏȽ«È365betÌåÓýÔÚÏßâµÄ¶þ²æ²éÕÒÊ÷ת»¯ÎªÀàËÆÓÚÁ´±íµÄÊ÷£¬³ÉΪÖ÷Á´»òÖ÷¸É£¨backbone or vine£©£»
- ΧÈÆÖ÷Á´Öеڶþ¸ö½ÚµãµÄ¸¸½Úµã£¬·´¸´½«ÆäÐýת£¬½«Õâ¿Ã±»ÀÉìµÄÊ÷ÔÚһϵÁв½ÖèÖÐת»¯ÎªÍêȫƽºâµÄÊ÷£»
µÚÒ»½×¶Î£ºÓÒÐýתÐγÉÖ÷Á´
ÆäÖÐÉæ¼°Ðýת£¨×óÐýת¡¢ÓÒÐýת£©µÄ²Ù×÷£¬365betÌåÓýÔÚÏßÃÇÏÈ¿´Ò»ÏÂÓÒÐýתµÄÂß¼£¬×óÐýתÓëÓÒÐýת¶Ô³Æ£¬Î±´úÂëÈçÏ£º
/************************************************************************
* ×Ó½Úµã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ÉèÖÃΪËüµÄÓÒ×ӽڵ㣻Æä¹ý³ÌÈçÏÂͼËùʾ£º
¿ÉÒÔ¿´µ½£¬ÓÒÐýµÄ¹ý³Ì¾ÍÊDz»¶Ï°Ñ×ó×ÓÊ÷Ðýתµ½Ö÷Á´µÄ¹ý³Ì¡£
µÚ¶þ½×¶Î£º×óÐýתת»»ÎªÆ½ºâÊ÷
ÓÒÐýתÐγÉÖ÷Á´ºó£¬Ï¸ö½×¶ÎÐèÒª×óÐýת£¬365betÌåÓýÔÚÏßÃÇ¿´Ò»ÏÂ×óÐýת£¬·ÖÎö˼·ÓëÓÒÐýתÏàͬ£¬ÏÂͼÖнڵã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×÷Ϊ×ó×Ó½Úµãͨ¹ýÓÒÐýתÐγÉÖ÷Á´ºó£¬¿ªÊ¼µÚ¶þ½×¶Î£ºÖ÷Á´×ª»»ÎªÆ½ºâÊ÷£ºÎ±´úÂëÈçÏ£º
// ÐèҪעÒâµÄÊÇ£¬Ã¿´Î˳×ÅÖ÷Á´ÏòϲÙ×÷ʱ£¬Ã¿¸ôÁ½¸ö½Úµã£¬¶¼Î§ÈÆÆ丸½Úµã½øÐÐÐýת
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¸ö½ÚµãΧÈÆÆ丸½Úµã½øÐÐÐýת£¨»òÕß˵ÊÇÿ´Î´ÓÖ÷Á´¸ù½Úµã¿ªÊ¼£¬Å¼Êý½ÚµãΧÈÆÆæÊý½Úµã×óÐýת£©¡£¿ÉÒÔ¿´µ½£¬×óÐýת¾ÍÊDz»¶Ï½«×óÓÒ×ÓÊ÷½øÐÐƽºâµÄ¹ý³Ì¡£
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