Arbori Binari de Căutare și Arbori AVL
Arbori Binari de Căutare și Arbori AVL¶
Arborele Binar de Căutare (BST)¶
Un arbore binar de căutare este un arbore binar în care fiecare nod respectă proprietatea:
$$\text{stânga}(x) < x < \text{dreapta}(x)$$
Toate valorile din subarborele stâng sunt mai mici decât nodul curent, iar cele din subarborele drept sunt mai mari. Această regulă se aplică recursiv la fiecare nod.
De ce contează?¶
Un BST echilibrat oferă operații de căutare, inserare și ștergere în $O(\log n)$. Comparativ, într-o listă sortată căutarea este $O(\log n)$, dar inserarea e $O(n)$. BST-ul rezolvă ambele eficient.
Implementare¶
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self._insert(self.root, key)
def _insert(self, node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = self._insert(node.left, key)
elif key > node.key:
node.right = self._insert(node.right, key)
return node
def search(self, key):
return self._search(self.root, key)
def _search(self, node, key):
if node is None or node.key == key:
return node
if key < node.key:
return self._search(node.left, key)
return self._search(node.right, key)
Parcurgeri¶
Cele trei parcurgeri clasice ale unui arbore binar:
def inorder(node):
"""Stânga → Rădăcină → Dreapta — produce elementele SORTATE"""
if node:
inorder(node.left)
print(node.key, end=" ")
inorder(node.right)
def preorder(node):
"""Rădăcină → Stânga → Dreapta — util pentru serializare"""
if node:
print(node.key, end=" ")
preorder(node.left)
preorder(node.right)
def postorder(node):
"""Stânga → Dreapta → Rădăcină — util pentru ștergere"""
if node:
postorder(node.left)
postorder(node.right)
print(node.key, end=" ")
Observație cheie: Parcurgerea inorder a unui BST produce elementele în ordine crescătoare. Aceasta este o consecință directă a proprietății BST.
Ștergerea unui nod¶
Ștergerea este operația cea mai complexă. Există trei cazuri:
- Nodul e frunză — pur și simplu îl eliminăm
- Nodul are un singur copil — îl înlocuim cu acel copil
- Nodul are doi copii — îl înlocuim cu succesorul inorder (cel mai mic element din subarborele drept)
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return None
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
# Cazul 1 și 2: frunză sau un singur copil
if node.left is None:
return node.right
if node.right is None:
return node.left
# Cazul 3: doi copii — găsim succesorul inorder
successor = self._min_node(node.right)
node.key = successor.key
node.right = self._delete(node.right, successor.key)
return node
def _min_node(self, node):
while node.left:
node = node.left
return node
Problema BST-ului: Degenerarea¶
Dacă inserăm elementele [1, 2, 3, 4, 5] într-un BST, obținem o listă liniară — fiecare nod are doar copil drept. Toate operațiile devin $O(n)$. Soluția: arborii echilibrați.
Arbori AVL¶
Un arbore AVL (Adelson-Velsky și Landis, 1962) este un BST în care, pentru fiecare nod, diferența de înălțime dintre subarborele stâng și drept este cel mult 1:
$$|\text{height}(\text{left}) - \text{height}(\text{right})| \leq 1$$
Această proprietate se numește factorul de echilibru (balance factor).
Rotații¶
Când o inserare sau ștergere încalcă echilibrul, se aplică rotații pentru a restabili proprietatea AVL. Există patru cazuri:
Rotație simplă la dreapta (cazul Stânga-Stânga):
def _rotate_right(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self._height(z.left), self._height(z.right))
y.height = 1 + max(self._height(y.left), self._height(y.right))
return y # y devine noua rădăcină a subarborelui
Rotație simplă la stânga (cazul Dreapta-Dreapta):
def _rotate_left(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self._height(z.left), self._height(z.right))
y.height = 1 + max(self._height(y.left), self._height(y.right))
return y
Inserare cu reechilibrare¶
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def _height(self, node):
return node.height if node else 0
def _balance_factor(self, node):
return self._height(node.left) - self._height(node.right) if node else 0
def insert(self, root, key):
# 1. Inserare BST normală
if not root:
return AVLNode(key)
if key < root.key:
root.left = self.insert(root.left, key)
elif key > root.key:
root.right = self.insert(root.right, key)
else:
return root # duplicate ignorate
# 2. Actualizăm înălțimea
root.height = 1 + max(self._height(root.left), self._height(root.right))
# 3. Verificăm echilibrul
bf = self._balance_factor(root)
# Stânga-Stânga → rotație dreapta
if bf > 1 and key < root.left.key:
return self._rotate_right(root)
# Dreapta-Dreapta → rotație stânga
if bf < -1 and key > root.right.key:
return self._rotate_left(root)
# Stânga-Dreapta → rotație stânga pe copil, apoi dreapta
if bf > 1 and key > root.left.key:
root.left = self._rotate_left(root.left)
return self._rotate_right(root)
# Dreapta-Stânga → rotație dreapta pe copil, apoi stânga
if bf < -1 and key < root.right.key:
root.right = self._rotate_right(root.right)
return self._rotate_left(root)
return root
Complexitate AVL¶
| Operație | Complexitate |
|---|---|
| Căutare | $O(\log n)$ |
| Inserare | $O(\log n)$ |
| Ștergere | $O(\log n)$ |
Înălțimea unui arbore AVL cu $n$ noduri este strict $O(\log n)$, ceea ce garantează performanța.
Exerciții¶
- Inserați secvența
[10, 20, 30, 25, 28, 27]într-un arbore AVL și desenați arborele după fiecare rotație - Implementați ștergerea cu reechilibrare într-un arbore AVL
- Demonstrați că înălțimea unui arbore AVL cu $n$ noduri este $\leq 1.44 \cdot \log_2(n)$