PAT.1066 Root of AVL Tree - AVL树的构造

PAT.1066 Root of AVL Tree - AVL树的构造

题目链接
题目给出插入顺序，要求根据插入顺序构建AVL树，并给出AVL树最终的根。
一下子想不到什么取巧的办法，老老实实构建AVL树吧。
趁机复习一下AVL树的概念：

• AVL树是一种二叉排序树，且在插入的过程中通过旋转 *** 作来实现平衡(即以任一节点为根，其左子树深度与右子树深度的差之绝对值不超过1)

顺便再复习一下旋转的概念：
旋转往往发生在形如(此处以RR失衡为例)
 root
   \
  child1
    \
   child2
的三代节点中，且root是失衡的最小子树的根，child1和child2为root指向导致失衡的新插入节点的路径上的两个相邻子节点。
而旋转 *** 作就是将这三个节点转换，使得值处在中间的那个节点为另外两者的父节点。
假设上面的例子中root < child1 < child2，则通过旋转将其变换为形如
  child1
  / \
root  child2
的结构，并且child1的左子树成为root的右子树，其余LL,LR,RL三种情况也都是类似的处理方式。

题解

思路很简单，代码就是根据思路一点点模拟。
其中判断失衡类型的部分有大段重复代码，写的比较累赘，可以考虑合并优化，或者用递归求解。

#include

using namespace std;
typedef long long ll;

struct node{
    int num;
    int leftHeight;
    int rightHeight;
    node* parent;
    node* leftChild;
    node* rightChild;
};

int n,t;
node *root,nodes[25];

node* findInsertParent(int num){
    node* nodePtr = root;
    node* preNode = root;
    while(nodePtr != nullptr){
        if(num > nodePtr->num){
            preNode = nodePtr;
            nodePtr = nodePtr->rightChild;
        }else{
            preNode = nodePtr;
            nodePtr = nodePtr->leftChild;
        }
    }
    return preNode;
}

//从根开始更新高度,返回以currentRoot为根的子树的深度
int updateHeight(node* currentRoot){
    if(currentRoot->leftChild != nullptr) currentRoot->leftHeight = updateHeight(currentRoot->leftChild);
    else currentRoot->leftHeight = 0;
    if(currentRoot->rightChild != nullptr) currentRoot->rightHeight = updateHeight(currentRoot->rightChild);
    else currentRoot->rightHeight = 0;
    return 1 + max(currentRoot->leftHeight,currentRoot->rightHeight);
}

int main(){
    cin>>n;
    for(int i = 0 ; i < n ; ++i){
        cin>>t;
        nodes[i] = (node){t,0,0,nullptr,nullptr,nullptr};
        if(root == nullptr) root = &nodes[i];
        else{
            node* parentNode = findInsertParent(t);
            if(t > parentNode->num){
                //插入右侧
                nodes[i].parent = parentNode;
                parentNode->rightChild = &nodes[i];
            }else{
                //插入左侧
                nodes[i].parent = parentNode;
                parentNode->leftChild = &nodes[i];
            }
            updateHeight(root);
            //插入完毕，回溯找到失衡最小子树的根
            node* imbalancedRoot = &nodes[i];
            //维护叶子结点到失衡最小子树的根的路径
            vector<node*> imbalancedPath;
            while(imbalancedRoot != nullptr){
                if(abs(imbalancedRoot->leftHeight - imbalancedRoot->rightHeight) > 1){
                    //失衡且imbalancedRoot为失衡最小子树的根
                    node* imbalancedChild1 = imbalancedPath[imbalancedPath.size() - 1];
                    node* imbalancedChild2 = imbalancedPath[imbalancedPath.size() - 2];
                    node* balancedRoot = imbalancedRoot->parent;
                    //开始判断失衡类型
                    if(imbalancedChild1 == imbalancedRoot->leftChild){
                        if(imbalancedChild2 == imbalancedChild1->leftChild){
                            //LL
                            if(balancedRoot == nullptr){
                                root = imbalancedChild1;
                                imbalancedChild1->parent = nullptr;
                            }else if(balancedRoot->leftChild == imbalancedRoot){
                                balancedRoot->leftChild = imbalancedChild1;
                                imbalancedChild1->parent = balancedRoot;
                            }else if(balancedRoot->rightChild == imbalancedRoot){
                                balancedRoot->rightChild = imbalancedChild1;
                                imbalancedChild1->parent = balancedRoot;
                            }
                            imbalancedRoot->leftChild = imbalancedChild1->rightChild;
                            if(imbalancedChild1->rightChild != nullptr) imbalancedChild1->rightChild->parent = imbalancedRoot;
                            imbalancedChild1->rightChild = imbalancedRoot;
                            imbalancedRoot->parent = imbalancedChild1;
                        }else if(imbalancedChild2 == imbalancedChild1->rightChild){
                            //LR
                            if(balancedRoot == nullptr){
                                root = imbalancedChild2;
                                imbalancedChild2->parent = nullptr;
                            }else if(balancedRoot->leftChild == imbalancedRoot){
                                balancedRoot->leftChild = imbalancedChild2;
                                imbalancedChild2->parent = balancedRoot;
                            }else if(balancedRoot->rightChild == imbalancedRoot){
                                balancedRoot->rightChild = imbalancedChild2;
                                imbalancedChild2->parent = balancedRoot;
                            }
                            imbalancedChild1->rightChild = imbalancedChild2->leftChild;
                            if(imbalancedChild2->leftChild != nullptr) imbalancedChild2->leftChild->parent = imbalancedChild1;
                            imbalancedChild2->leftChild = imbalancedChild1;
                            imbalancedChild1->parent = imbalancedChild2;
                            imbalancedRoot->leftChild = imbalancedChild2->rightChild;
                            if(imbalancedChild2->rightChild != nullptr) imbalancedChild2->rightChild->parent = imbalancedRoot;
                            imbalancedChild2->rightChild = imbalancedRoot;
                            imbalancedRoot->parent = imbalancedChild2;
                        }
                    }else if(imbalancedChild1 == imbalancedRoot->rightChild){
                        if(imbalancedChild2 == imbalancedChild1->leftChild){
                            //RL
                            if(balancedRoot == nullptr){
                                root = imbalancedChild2;
                                imbalancedChild2->parent = nullptr;
                            }else if(balancedRoot->leftChild == imbalancedRoot){
                                balancedRoot->leftChild = imbalancedChild2;
                                imbalancedChild2->parent = balancedRoot;
                            }else if(balancedRoot->rightChild == imbalancedRoot){
                                balancedRoot->rightChild = imbalancedChild2;
                                imbalancedChild2->parent = balancedRoot;
                            }
                            imbalancedChild1->leftChild = imbalancedChild2->rightChild;
                            if(imbalancedChild2->rightChild != nullptr) imbalancedChild2->rightChild->parent = imbalancedChild1;
                            imbalancedChild2->rightChild = imbalancedChild1;
                            imbalancedChild1->parent = imbalancedChild2;
                            imbalancedRoot->rightChild = imbalancedChild2->leftChild;
                            if(imbalancedChild2->leftChild != nullptr) imbalancedChild2->leftChild->parent = imbalancedRoot;
                            imbalancedChild2->leftChild = imbalancedRoot;
                            imbalancedRoot->parent = imbalancedChild2;
                        }else if(imbalancedChild2 == imbalancedChild1->rightChild){
                            //RR
                            if(balancedRoot == nullptr){
                                root = imbalancedChild1;
                                imbalancedChild1->parent = nullptr;
                            }else if(balancedRoot->leftChild == imbalancedRoot){
                                balancedRoot->leftChild = imbalancedChild1;
                                imbalancedChild1->parent = balancedRoot;
                            }else if(balancedRoot->rightChild == imbalancedRoot){
                                balancedRoot->rightChild = imbalancedChild1;
                                imbalancedChild1->parent = balancedRoot;
                            }
                            imbalancedRoot->rightChild = imbalancedChild1->leftChild;
                            if(imbalancedChild1->leftChild != nullptr) imbalancedChild1->leftChild->parent = imbalancedRoot;
                            imbalancedChild1->leftChild = imbalancedRoot;
                            imbalancedRoot->parent = imbalancedChild1;
                        }
                    }
                    updateHeight(root);
                    break;
                }else{
                    imbalancedPath.push_back(imbalancedRoot);
                    imbalancedRoot = imbalancedRoot->parent;
                }
            }
        }
    }
    cout<<root->num;
}