Root of AVL Tree (25)

1、题意

���所有数插入后，根节点是哪个数

2、两种代码：

2.1 代码1：

#include#includeusing namespace std;const int N = 30; int l[N],r[N],v[N],h[N],idx;void update(int u)// 计算子树的高度 {h[u] = max(h[l[u]],h[r[u]]) + 1;} void R(int &u)// 右旋 {int p = l[u];l[u] = r[p],r[p] = u;update(u),update(p);u = p; }void L(int &u){int p = r[u];r[u] = l[p],l[p] = u;update(u),update(p);u = p;}int get_balance(int u){//左子树高度减去右子树高度return h[l[u]] - h[r[u]]; }void insert(int &u,int w){if(!u) u = ++idx,v[u] = w; // 一开始u = 0 else if(wvalue){taller = false;return false;}if(value value){if(!InsertAVL(pRoot->lchild,value,taller))return false;if(taller){switch(pRoot->BF){case LH: // 原来左边偏高，还是插在了左边LeftBalance(pRoot);taller = false;// 处理后高度不变；break;case EH:// 原本等高，插左边后长高pRoot->BF = LH;taller = true;break;case RH:// 原本右侧高，插在左侧，高度不变 pRoot->BF = EH;taller = false;break; }}}else {if(!InsertAVL(pRoot->rchild,value,taller))return false;if(taller){switch(pRoot->BF){case LH:// 原本左侧高，插在了右侧，登高pRoot->BF = EH;taller = false;break;case EH:pRoot->BF = RH;taller = true;break;case RH:;RightBalance(pRoot);taller = false;break;}}}}return true;}// 左旋，以pRoot为根节点的树进行左旋处理，并调整好父子连接void LeftRotation(AVLTreeNode* &pRoot){// pRoot现在为失衡节点，pRitht为pRoot的右子节点，pRoot,pRitht进行左旋处理AVLTreeNode* pRight = pRoot->rchild;pRoot->rchild = pRight->lchild;pRight->lchild = pRoot;pRoot = pRight;}// 右旋，以pRoot为根节点的树进行右旋处理，并调整好父子连接void RightRotation(AVLTreeNode* &pRoot){// pRoot现在为失衡节点，pleft为pRoot的左子节点，对pRoot和pLeft进行右旋AVLTreeNode *pLeft = pRoot->lchild;pRoot->lchild = pLeft->rchild;pLeft->rchild = pRoot;pRoot = pLeft;}// 对左边的失衡部分进行平衡处理void LeftBalance(AVLTreeNode* &pRoot){AVLTreeNode *pLeft,*pLeftRight;pLeft = pRoot->lchild;switch(pLeft->BF){case LH: // LL型pRoot->BF = EH;pLeft->BF = EH;RightRotation(pRoot);break;case RH: // LR型 pLeftRight = pLeft->rchild;switch(pLeftRight->BF){case LH:pRoot->BF = RH;pLeft->BF = EH;break;case EH:pRoot->BF = EH;pLeft->BF = EH;break;case RH:pRoot->BF = EH;pLeft->BF = LH;break;}pLeftRight->BF = EH;LeftRotation(pRoot->lchild);RightRotation(pRoot);// 这里不能写出pleftbreak;}}void RightBalance(AVLTreeNode* &pRoot){AVLTreeNode* pRight,*pRightLeft;pRight = pRoot->rchild;switch(pRight->BF){case RH: // RR型pRoot->BF = pRight->BF = EH;LeftRotation(pRoot);break;case LH: // RL型pRightLeft = pRight->lchild;switch(pRightLeft->BF){case LH:pRoot->BF = EH;pRight->BF = RH;break;case EH:pRoot->BF = EH;pRight->BF = EH;break;case RH:pRoot->BF = LH;pRight->BF = EH;break;}pRightLeft->BF = EH;RightRotation(pRoot->rchild);LeftRotation(pRoot);break;}}