⬆︎
×

[PAT-A] 1066 Root of AVL Tree

Java

import java.util.Scanner;

public class Main {
    static final int N = 30;

    static int n;
    static int[] l = new int[N];
    static int[] r = new int[N];
    static int[] w = new int[N];
    static int[] h = new int[N];
    static int idx = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        int root = 0;
        for (int i = 0; i < n; ++i) {
            int x = scanner.nextInt();
            root = insert(root, x);
        }

        System.out.println(w[root]);
        scanner.close();
    }

    static void update(int u) {
        h[u] = Math.max(h[l[u]], h[r[u]]) + 1;
    }

    static int getBF(int u) {
        return h[l[u]] - h[r[u]];
    }

    static int L(int u) {
        int p = r[u];
        r[u] = l[p];
        l[p] = u;
        update(u);
        update(p);
        return p;
    }

    static int R(int u) {
        int p = l[u];
        l[u] = r[p];
        r[p] = u;
        update(u);
        update(p);
        return p;
    }

    static int insert(int u, int x) {
        if (u == 0) {
            u = ++idx;
            w[u] = x;
            h[u] = 1; // Initialize height at 1
        } else if (x < w[u]) {
            l[u] = insert(l[u], x);
            if (getBF(u) == 2) {
                if (getBF(l[u]) == 1) {
                    u = R(u);
                } else if (getBF(l[u]) == -1) {
                    l[u] = L(l[u]);
                    u = R(u);
                }
            }
        } else {
            r[u] = insert(r[u], x);
            if (getBF(u) == -2) {
                if (getBF(r[u]) == -1) {
                    u = L(u);
                } else if (getBF(r[u]) == 1) {
                    r[u] = R(r[u]);
                    u = L(u);
                }
            }
        }

        update(u);
        return u;
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;

int n;
int l[N], r[N], w[N], h[N], idx;

void update(int u) {
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}

int getBF(int u) {
    return h[l[u]] - h[r[u]];
}

void L(int &u) {
    int p = r[u];
    r[u] = l[p], l[p] = u;
    update(u), update(p);
    u = p;
}

void R(int &u) {
    int p = l[u];
    l[u] = r[p], r[p] = u;
    update(u), update(p);
    u = p;
}

void insert(int &u, int x) {
    if (!u) {
        u = ++idx;
        w[u] = x;
    } else if (x < w[u]) {
        insert(l[u], x);
        if (getBF(u) == 2) {
            if (getBF(l[u]) == 1) R(u);
            else if (getBF(l[u]) == -1) L(l[u]), R(u);
        }
    } else {
        insert(r[u], x);
        if (getBF(u) == -2) {
            if (getBF(r[u]) == -1) L(u);
            else if (getBF(r[u]) == 1) R(r[u]), L(u);
        }
    }

    update(u);
}

int main() {
    scanf("%d", &n);

    int root = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        insert(root, x);
    }

    printf("%d\n", w[root]);
    return 0;
}

发表评论