Algorithmes d'arbreIntermediate

Plus bas ancêtre commun (LCA)

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.

#tree#binary-tree#recursion#ancestry

Complexity Analysis

Time (Average)

O(n)

Expected case performance

Space

O(h)

Memory requirements

Time (Best)

O(n)

Best case performance

Time (Worst)

O(n)

Worst case performance

Binary Tree (level-order, comma-separated)

Use 'null' for empty nodes

Node p

Node q

Example Trees:

How it works

• Recursively traverse the tree
• Find nodes p and q in subtrees
• LCA is where both are found
• O(n) time, O(h) space
• Used in version control systems

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

Arbre AVL

Advanced

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.

Back to Algorithmes d'arbre