Albero binario di ricerca bilanciato

Questa voce sull'argomento matematica dell'informazione e della comunicazione è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

In informatica, un albero binario di ricerca bilanciato è un albero binario di ricerca la cui altezza, grazie a particolari condizioni che la sua struttura deve soddisfare, rimane limitata. Queste condizioni implicano delle operazioni di inserimento ed eliminazione più complesse rispetto a quelle di semplici alberi binari, ma garantiscono che esse vengano eseguite in O(log n).

Esempi

Alcune strutture di dati che implementano questo tipo di alberi sono:

Albero AA
Albero AVL
B-Albero
RB-Albero
Albero splay

Altri progetti

Wikimedia Commons

Wikimedia Commons contiene immagini o altri file sull'albero binario di ricerca bilanciato

V · D · M Strutture dati
Tipi	Collezione · Container
Astratte	Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset)
Array	Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso
Collegate	Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR
Alberi	B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario
Grafi	Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico
Alberi di partizionamento dei dati spaziali	Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree
Lista di strutture dati