平衡二叉树（AVL树）

一、平衡二叉树的概念 请看链接：http://baike.baidu.com/view/593144.htm

二、平衡二叉树的算法逻辑 请看链接：http://sjjg.js.zwu.edu.cn/SFXX/chazhao/chazhao7.3.2.html

实现代码如下：

/*<br /> FileName: binaryBalanceTree.cpp<br /> Author: ACb0y<br /> Create Time: 2011年2月19日20:41:59<br /> Last modify Time:<br /> */<br /> #include <iostream><br /> using namespace std;<br /> //平衡因子(balance factor)的值<br /> //左子树比右子树高一<br /> #define LH 1<br /> //左子树和右子树一样高<br /> #define EH 0<br /> //左子树比右子树低一<br /> #define RH -1<br /> //数据类型定义<br /> typedef int type;<br /> //平衡二叉树的节点<br /> typedef struct BSTNode<br /> {<br /> type data;<br /> int bf;<br /> BSTNode * lchild;<br /> BSTNode * rchild;<br /> }BSTNode;<br /> typedef BSTNode * BSTree;<br /> /*<br /> 函数名：void leftRotate(BSTree & root);<br /> 功能：左旋<br /> 参数：<br /> 输入：<br /> root (BSTree &): 树的根<br /> 输出：无<br /> 返回值：无<br /> */<br /> void leftRotate(BSTree & root)<br /> {<br /> BSTree rc = root->rchild;<br /> root->rchild = rc->lchild;<br /> rc->lchild = root;<br /> root = rc;<br /> }<br /> /*<br /> 函数名：void R_Rotate(BSTree & root);<br /> 功能：右旋<br /> 参数：<br /> 输入：<br /> root (BSTree &): 树的根<br /> 输出：无<br /> 返回值：无<br /> */<br /> void rightRotate(BSTree & root)<br /> {<br /> BSTree lc = root->lchild;<br /> root->lchild = lc->rchild;<br /> lc->rchild = root;<br /> root = lc;<br /> }<br /> /*<br /> 函数名：void leftBalance(BSTree & root);<br /> 功能：对二叉树root进行左平衡处理(LL型和LR型)<br /> 参数：<br /> 输入：<br /> root (BSTree &): 二叉树跟节点<br /> 输出：无<br /> 返回值：无<br /> */<br /> void leftBalance(BSTree & root)<br /> {<br /> BSTree lc = root->lchild;<br /> switch (lc->bf)<br /> {<br /> //LL型的只需要进行右旋操作<br /> case LH:<br /> //右旋之后根和左子树都的平衡的<br /> root->bf = EH;<br /> lc->bf = EH;<br /> //右旋操作<br /> rightRotate(root);<br /> break;<br /> //LR型的需要进行左旋操作，然后右旋操作<br /> case RH:<br /> BSTree rc = lc->rchild;<br /> switch (rc->bf)<br /> {<br /> case LH:<br /> root->bf = RH;<br /> lc->bf = EH;<br /> break;<br /> case EH:<br /> root->bf = EH;<br /> lc->bf = EH;<br /> break;<br /> case RH:<br /> root->bf = EH;<br /> lc->bf = LH;<br /> break;<br /> }<br /> rc->bf = EH;<br /> leftRotate(root->lchild);<br /> rightRotate(root);<br /> break;<br /> }<br /> }<br /> /*<br /> 函数名：void rightBalance(BSTree & root);<br /> 功能：对二叉树root进行左平衡处理(RR型和RL型)<br /> 参数：<br /> 输入：<br /> root (BSTree &): 二叉树跟节点<br /> 输出：无<br /> 返回值：无<br /> */<br /> void rightBalance(BSTree & root)<br /> {<br /> BSTree rc = root->rchild;<br /> switch (rc->bf)<br /> {<br /> //RR型只需要做左旋操作<br /> case RH:<br /> root->bf = EH;<br /> rc->bf = EH;<br /> //左旋操作<br /> leftRotate(root);<br /> break;<br /> //RL型需要先做右旋操作，然后做左旋操作<br /> case LH:<br /> BSTree lc = rc->lchild;<br /> switch (lc->bf)<br /> {<br /> case LH:<br /> root->bf = EH;<br /> rc->bf = RH;<br /> break;<br /> case EH:<br /> root->bf = EH;<br /> rc->bf = EH;<br /> break;<br /> case RH:<br /> root->bf = LH;<br /> rc->bf = EH;<br /> break;<br /> }<br /> lc->bf = EH;<br /> rightRotate(root->rchild);<br /> leftRotate(root);<br /> break;<br /> }<br /> }<br /> /*<br /> 函数名：bool insert(BSTree & root, type data, bool & taller);<br /> 功能：把元素data插入平衡二叉树root中<br /> 参数：<br /> 输入：<br /> root (BSTree &): 平衡二叉树的根<br /> data (type): 要插入的元素<br /> taller (bool): 标记插入元素后树高是否发生变化(taller == true表示树变高，否则不变高)<br /> 输出：无<br /> 返回值：<br /> true (bool): 插入成功<br /> false (bool): 插入失败<br /> */<br /> bool insert(BSTree & root, type data, bool & taller)<br /> {<br /> if (NULL == root)<br /> {<br /> root = (BSTree)malloc(sizeof(BSTNode));<br /> root->rchild = NULL;<br /> root->lchild = NULL;<br /> root->data = data;<br /> root->bf = EH;<br /> taller = true;<br /> }<br /> else<br /> {<br /> //该元素已经在平衡二叉树中存在了<br /> if (data == root->data)<br /> {<br /> taller = false;<br /> return false;<br /> }<br /> //插入左子树<br /> else if (data < root->data)<br /> {<br /> if (!insert(root->lchild, data, taller))<br /> {<br /> return false;<br /> }<br /> //插入成功，并且树变高了<br /> if (taller)<br /> {<br /> switch (root->bf)<br /> {<br /> case LH:<br /> leftBalance(root);<br /> //平衡二叉树做完左平衡操作后<br /> //树高没有变化，故taller = false<br /> taller = false;<br /> break;<br /> case EH:<br /> root->bf = LH;<br /> //原来是平衡的故插入一个元素后<br /> //树高必然变高<br /> taller = true;<br /> break;<br /> case RH:<br /> root->bf = EH;<br /> //原来是右子树比左子树高，但是当向左子树中<br /> //插入一个元素的时候，树变平衡了，故taller = false<br /> taller = false;<br /> break;<br /> default:<br /> break;<br /> }<br /> }<br /> }<br /> //插入右子树<br /> else<br /> {<br /> if (!insert(root->rchild, data, taller))<br /> {<br /> return 0;<br /> }<br /> if (taller)<br /> {<br /> switch (root->bf)<br /> {<br /> case LH:<br /> root->bf = EH;<br /> taller = false;<br /> break;<br /> case EH:<br /> root->bf = RH;<br /> taller = true;<br /> break;<br /> case RH:<br /> rightBalance(root);<br /> taller = false;<br /> break;<br /> }<br /> }<br /> }<br /> }<br /> return true;<br /> }<br /> /*<br /> 函数名：type * search(BSTree & root, type data);<br /> 功能：在平衡二叉树中查找data节点<br /> 参数：<br /> 输入：<br /> root (BSTree &): 平衡二叉树的根<br /> data (type): 要查找的数据<br /> 输出：无<br /> 返回值：指向data的指针<br /> */<br /> type * search(BSTree & root, type data)<br /> {<br /> if (NULL == root)<br /> {<br /> return NULL;<br /> }</p> <p> if (root->data == data)<br /> {<br /> return &root->data;<br /> }<br /> else if (data < root->data)<br /> {<br /> return search(root->lchild, data);<br /> }<br /> else<br /> {<br /> return search(root->rchild, data);<br /> }<br /> }<br /> /*<br /> 函数名：void print(BSTree & root, char * format);<br /> 功能：输出平衡二叉树中的所有的元素（小->大，中序遍历）<br /> 参数：<br /> 输入：<br /> root (BSTree &): 平衡二叉树的根<br /> format (char *): 元素输出的格式<br /> 输出：无<br /> 返回值：无<br /> */<br /> void print(BSTree & root, char * format)<br /> {<br /> if (NULL == root)<br /> {<br /> return ;<br /> }<br /> print(root->lchild, format);<br /> printf(format, root->data);<br /> print(root->rchild, format);<br /> }<br /> /*<br /> 函数名：void clear(BSTree & root);<br /> 功能：释放平衡二叉树的空间<br /> 参数：<br /> 输入：<br /> root (BSTree &): 平衡二叉树的根<br /> 输出：无<br /> 返回值：无<br /> */<br /> void clear(BSTree & root)<br /> {<br /> if (NULL == root)<br /> {<br /> return ;<br /> }<br /> clear(root->lchild);<br /> clear(root->rchild);<br /> free(root);<br /> }<br /> int main()<br /> {<br /> BSTree root = NULL;<br /> bool taller = false;<br /> srand(time(NULL));<br /> int tmp;<br /> for (int i = 0; i < 10; ++i)<br /> {<br /> tmp = rand() % 16;<br /> bool flag = insert(root, tmp, taller);<br /> if (flag)<br /> {<br /> printf("%d insert success!/n", tmp);<br /> }<br /> else<br /> {<br /> printf("%d insert failure!/n", tmp);<br /> }<br /> }</p> <p> cout << "insert done" << endl;<br /> print(root, "%d ");<br /> cout << endl;<br /> for (int i = 0; i < 5; ++i)<br /> {<br /> tmp = rand() % 16;<br /> type * p = search(root, tmp);<br /> if (NULL == p)<br /> {<br /> printf("not found %d!/n", tmp);<br /> }<br /> else<br /> {<br /> printf("found %d!/n", *p);<br /> }<br /> }<br /> clear(root);<br /> cout << "clear done" << endl;<br /> return 0;<br /> }<br />  

运行结果如下：