Algorithmes d'arbreAdvanced

Arbre AVL

Premier arbre binaire de recherche auto-équilibré inventé en 1962 par Adelson-Velsky et Landis. Maintient l'équilibre de hauteur par des rotations, garantissant des opérations O(log n). Un équilibrage plus strict que les arbres rouge-noir le rend idéal pour les applications à forte consultation comme les bases de données et les systèmes de fichiers.

#tree#self-balancing#rotation#binary-search-tree

Complexity Analysis

Time (Average)

O(log n)

Expected case performance

Space

O(n)

Memory requirements

Time (Best)

O(log n)

Best case performance

Time (Worst)

O(log n)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 13•Section Notes

Values to Insert (comma-separated, max 10)

Watch rotations maintain balance!

Example Sets:

Rotation Types

• LL: Right rotation (left-heavy)
• RR: Left rotation (right-heavy)
• LR: Left-Right rotation
• RL: Right-Left rotation
• Balance factor: height(left) - height(right)
• O(log n) for insert, delete, search

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in Algorithmes d'arbre

Trie (Arbre préfixe)

Intermediate

Structure de données arborescente qui stocke les chaînes efficacement en partageant les préfixes communs. Chaque chemin de la racine à la feuille représente un mot ou une clé. Excelle dans l'autocomplétion, la vérification orthographique, les tables de routage IP et les implémentations de dictionnaire avec des opérations O(m) où m est la longueur de la clé.

O(m)

O(ALPHABET_SIZE × N × M)

treestring-algorithms

Start Learning

Plus bas ancêtre commun (LCA)

Intermediate

Trouve le nœud le plus profond qui est un ancêtre de deux nœuds donnés dans un arbre. Opération fondamentale dans les requêtes d'arbre avec des applications en biologie computationnelle (évolution des espèces), routage réseau et systèmes de contrôle de version. Divers algorithmes offrent différents compromis temps-espace.

Back to Algorithmes d'arbre