3010 - Bst - Revision history

Bonte Lucas Gabriel at 20:12, 3 January 2024

2024-01-03T20:12:39Z

← Older revision		Revision as of 20:12, 3 January 2024
Line 18:		Line 18:
	*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''1.000.000.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		*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'''.		*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:==		==Exemplul 1:==

	~~bst~~.in		'''bstin.txt'''

	10		10
	20 7 13 200 15 100 25 3 17 39		20 7 13 200 15 100 25 3 17 39
	~~bst.out~~

	3 7 13 15 17 20 25 39 100 200		'''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==

			<syntaxhighlight lang="python" line="1" start="1">

	class Node:		class Node:
Line 80:		Line 96:
	except IndexError:		except IndexError:
	file_out.write("Datele de intrare nu corespund restrictiilor impuse")		file_out.write("Datele de intrare nu corespund restrictiilor impuse")

			</syntaxhighlight>

Bonte Lucas Gabriel at 17:25, 3 January 2024

2024-01-03T17:25:31Z

← Older revision		Revision as of 17:25, 3 January 2024
Line 1:		Line 1:
	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.		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		==Cerința==
	~~Dându-se un șir de n numere naturale, să se ordoneze crescător utilizând un BST.~~

	~~Date~~ de ~~intrare~~		Dându-se un șir de '''n''' numere naturale, să se ordoneze crescător utilizând un '''BST'''.
	~~Fișierul de intrare bst.in conține pe prima linie numărul n, iar pe a doua linie~~ n numere naturale ~~separate prin spații~~.

	Date de ieșire		==Date de intrare==
	Fișierul de ieșire ~~bst~~.~~out~~ va conține pe prima linie, separate prin spațiu, cele n numere din șir, ordonate crescător.
			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:==

	~~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.
	~~Exemplu:~~
	bst.in		bst.in

Bonte Lucas Gabriel: Pagină nouă: 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 bst.in conține pe prima linie numă...

2024-01-03T16:00:56Z

Pagină nouă: 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 bst.in conține pe prima linie numă...

New page

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 bst.in 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 bst.out 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.
Exemplu:
bst.in

10
20 7 13 200 15 100 25 3 17 39
bst.out

3 7 13 15 17 20 25 39 100 200

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")