PAT 解题报告 1066. Root of AVL Tree (25)

Root of AVL Tree题目描述:

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

    

 

    

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

就是给出一系列的需要插入的节点, 让你求出插入这N个节点以后最终的AVL tree的root是什么.

Root of AVL Tree算法分析:

常规题吧, 就是实现以下AVL Tree的插入操作, 为了保证AVL Tree是平衡的, 需要有四种rotation去重组不平衡的节点. 四种case分别是L-L左孩子的左子树太深, L-R左孩子的右子树太深, R-R右孩子的右子树太深, R-L右孩子的左子树太深. 其中两两对称, L-L 和 R-R可以用single rotation完成平衡操作, L-R和R-L可以用double rotation(其实也就是两次single rotation), 关于single rotation看那本教材吧…“数据结构与算法分析”. 下面是可以AC的代码:

#include <cstdio>
#include <cmath>
#include <algorithm>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    int height;
    TreeNode(int v): val(v), left(NULL), right(NULL), height(0) {}
    TreeNode(): val(0), left(NULL), right(NULL), height(0) {}
};

int getHeight(TreeNode *node) {
    if(NULL == node) return -1;
    return node->height;
}

TreeNode *singleRoateLeft(TreeNode *k2) {
    TreeNode *k1 = k2->left;
    k2->left = k2->right;
    k1->right = k2;

    k2->height = std::max(getHeight(k2->left), getHeight(k2->right)) + 1;
    k1->height = std::max(getHeight(k1->left), getHeight(k1->right)) + 1;
    return k1;
}

TreeNode *singleRoateRight(TreeNode *k1) {
    TreeNode *k2 = k1->right;
    k1->right= k2->left;
    k2->left = k1;

    k1->height = std::max(getHeight(k1->left), getHeight(k1->right)) + 1;
    k2->height = std::max(getHeight(k2->left), getHeight(k2->right)) + 1;
    return k2;
}

TreeNode *doubleRoateLeft(TreeNode *k3) {
    k3->left = singleRoateRight(k3->left);
    return singleRoateLeft(k3);
}

TreeNode *doubleRoateRight(TreeNode *k1) {
    k1->right = singleRoateLeft(k1->right);
    return singleRoateRight(k1);
}

bool isBalanced(TreeNode *left, TreeNode *right) {
   return std::abs(getHeight(left) - getHeight(right)) < 2;
}

TreeNode *insert(int v, TreeNode *root) {
    if(NULL == root) {
        root = new TreeNode(v);
        return root;
    }
    if(v < root->val) {
        root->left = insert(v, root->left);
        if(!isBalanced(root->left, root->right)) {
            // test single or double
            if(v < root->left->val)
                root = singleRoateLeft(root);
            else
                root = doubleRoateLeft(root);
        }
    }
    else {
        root->right = insert(v, root->right);
        if(!isBalanced(root->left, root->right)) {
            if(v > root->right->val)
                root = singleRoateRight(root);
            else
                root = doubleRoateRight(root);
        }
    }
    root->height = std::max(getHeight(root->left), getHeight(root->right)) + 1;
    return root;
}

int main() {
    int n, v;
    scanf("%d", &n);
    TreeNode *root = NULL;

    while(n--)  {
        scanf("%d", &v);
        root = insert(v, root);
    }
    printf("%d\n", root->val);
    // destroy(root);
    return 0;
}

Root of AVL Tree注意点:

在重新构建不平衡的节点的时候注意节点的高度信息的更新. 别忘记更新高度信息.

 

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on October 11, 2013