3010 - Bst

Un arbore binar de căutare (BST – Binary Search Tree) este un arbore binar cu proprietatea că valoarea memorată într-un nod este mai mare decât valoarea memorată în orice nod din subarborele său stâng și este mai mică sau egală decât valoarea memorată în orice nod din subarborele său drept.

Cerința

Dându-se un șir de n numere naturale, să se ordoneze crescător utilizând un BST.

Date de intrare

Fișierul de intrare bstin.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire bstout.txt va conține pe prima linie, separate prin spațiu, cele n numere din șir, ordonate crescător.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• Această problemă este destinată învățării arborilor de căutare, deci recomandarea este să memorați mai întâi numerele într-un BST, apoi, cu o parcurgere în inordine să afișați șirul de numere ordonat crescător
• Se știe că există cazuri când un BST poate avea multe nivele și în consecință complexitatea sortării să fie chiar O(n x n). Un exemplu este atunci când șirul inițial este ordonat descrescător. Dar este garantat că testele au fost generate aleator, deci numărul de nivele din arbore va fi aproximativ egal cu log2n.

Exemplul 1:

bstin.txt

10
20 7 13 200 15 100 25 3 17 39

bstout.txt

Datele de intrare corespund restrictiilor impuse
3 7 13 15 17 20 25 39 100 200

Exemplul 2:

bstin.txt

bst

bstout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key


def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root


def inorder(root, fisier_out):
    if root:
        inorder(root.left, fisier_out)
        fisier_out.write(str(root.val) + " ")
        inorder(root.right, fisier_out)


def validare(nr):
    if len(nr) > 100000:
        raise ValueError
    for numar in nr:
        if numar < 0 or numar > 1000000000:
            raise ValueError
    file_out.write("Datele de intrare corespund restrictiilor impuse\n")


if __name__ == '__main__':
    file_in = open("bstin.txt", "r")
    file_out = open("bstout.txt", "w")
    try:
        n = int(file_in.readline())
        arr = list(map(int, file_in.readline().split()))
        validare(arr)
        r = Node(arr[0])
        for i in range(1, n):
            r = insert(r, arr[i])
        inorder(r, file_out)
        file_out.write('\n')
    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")