Ứng dụng của cây AVL ?

Xin chào các bạn!
Các bạn cho mình hỏi các ứng dụng cụ thể của cây AVL (cây nhị phân cân bằng)là gì ?

Trả lời:

Cân bằng AVL
Do Adel’son Vel’skki và Landis
AVL: Cây TKNP mà chiều cao của hai cây con của mọi nút chênh lệch nhiều nhất là 1.
*thêm một nút vào cây TKNP. Cây có thể mất cân bằng.
Cân bằng lại
r = root, tl = tree lelft, tr = tree right, h = high
* Xét cây AVL: tree T=(r,Tl,Tr) trong đó Tl có chiều cao hl và Tr có chiều cao hr
Giả sử nút thêm vào trên Tr.
Nếu hl=hr+1: sau khi thêm vẫn cân bằng
Nếu hl=hr : sau khi thêm vẫn cân bằng
Nếu hl=hr-1 thì sau khi thêm sẽ mất cân bằngcân bằng lại.
Tương tự nếu thêm nút vào Tl.
Nếu không cần bằng thì sử dụng 1 trong 4 phép quay là có thể cân bằng