1773 Problem A 算法9-9~9-12：平衡二叉樹的基本操作

問題 A: 算法9-9~9-12：平衡二叉樹的基本操作

時間限制: 1 Sec  記憶體限制: 32 MB

送出: 59  解決: 33

題目描述

平衡二叉樹又稱AVL樹，它是一種具有平衡因子的特殊二叉排序樹。平衡二叉樹或者是一棵空樹，或者是具有以下幾條性質的二叉樹：

1.       若它的左子樹不空，則左子樹上所有結點的值均小于它的根節點的值；

2.       若它的右子樹不空，則右子樹上所有結點的值均大于它的根節點的值；

3.       它的左右子樹也分别為平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。

若将二叉樹上結點的平衡因子定義為該結點的左子樹深度減去它的右子樹的深度，則平衡二叉樹上的所有結點的平衡因子隻可能為-1、0和1。隻要二叉樹上有一個結點的平衡因子的絕對值大于1，則這棵二叉樹就是不平衡的。

通過平衡二叉樹的性質不難得知，其插入、删除、查詢都操作的時間複雜度均為O(log2n)。

維持平衡二叉樹性質的操作可以被稱為旋轉。其中平衡二叉樹的右旋處理可以描述如下：

而其左旋處理與右旋正好相反，可以描述如下：

在本題中，讀入一串整數，首先利用這些整數構造一棵平衡二叉樹。另外給定多次查詢，利用構造出的平衡二叉樹，判斷每一次查詢是否成功。

輸入

輸入的第一行包含2個正整數n和k，分别表示共有n個整數和k次查詢。其中n不超過500，k同樣不超過500。

第二行包含n個用空格隔開的正整數，表示n個整數。

第三行包含k個用空格隔開的正整數，表示k次查詢的目标。

輸出

隻有1行，包含k個整數，分别表示每一次的查詢結果。如果在查詢中找到了對應的整數，則輸出1，否則輸出0。

請在每個整數後輸出一個空格，并請注意行尾輸出換行。

樣例輸入

8 3
1 3 5 7 8 9 10 15
9 2 5      

樣例輸出

1 0 1      

提示

在本題中，首先需要按照題目描述中的算法完成平衡二叉樹的構造過程，之後需要通過在平衡二叉樹中的不斷向下查找，将需要查詢的值與目前節點的值進行比較，直到确定被查詢的值是否存在。

通過課本中的性能分析部分，不難發現平衡二叉樹的查找、插入、删除等操作的時間複雜度均為O(log2n)，這是通過利用旋轉操作使二叉樹保持平衡狀态而保證的。

經驗總結

正确代碼

#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

struct node
{
    int data,height;
    node *lchild;
    node *rchild;
};
int getHeight(node * root)
{
    if(root==NULL)
        return 0;
    return root->height;
}
void updateHeight(node * root)
{
    root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}
int getBalanceFactor(node * root)
{
    return getHeight(root->lchild)-getHeight(root->rchild); 
}
void R(node * &root)
{
    node * temp=root->lchild;
    root->lchild=temp->rchild;
    temp->rchild=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}
void L(node * &root)
{
    node * temp=root->rchild;
    root->rchild=temp->lchild;
    temp->lchild=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}
void insert(node * &root, int x)
{
    if(root==NULL)
    {
        node * temp=new node;
        temp->data=x;
        temp->height=1;
        temp->rchild=temp->lchild=NULL;
        root=temp;
        return ;
    }
    if(x>root->data)
    {
        insert(root->rchild,x);
        updateHeight(root);
        if(getBalanceFactor(root)==-2)
        {
            if(getBalanceFactor(root->rchild)==-1)
            {
                L(root);
            }
            else if(getBalanceFactor(root->rchild)==1)
            {
                R(root->rchild);
                L(root);
            }
        }
    }
    else
    {
        insert(root->lchild,x);
        updateHeight(root);
        if(getBalanceFactor(root)==2)
        {
            if(getBalanceFactor(root->lchild)==-1)
            {
                L(root->lchild);
                R(root);
            }
            else if(getBalanceFactor(root->lchild)==1)
            {
                R(root);
            }
        }
    }
}
int search(node * root ,int x)
{
    if(root==NULL)
        return 0;
    if(root->data==x)
        return 1;
    else if(root->data<x)
        search(root->rchild,x);
    else
        search(root->lchild,x);
}
int main()
{
    int n,k,data;
    while(~scanf("%d %d",&n,&k))
    {
        node * root=NULL;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&data);
            insert(root,data);
        }
        for(int i=0;i<k;++i)
        {
            scanf("%d",&data);
            printf("%d ",search(root,data));
        }
        printf("\n");
    }
    return 0;
}