BaumalgorithmenIntermediate
Niedrigster gemeinsamer Vorfahre (LCA)
Findet den tiefsten Knoten, der ein Vorfahre von zwei gegebenen Knoten in einem Baum ist. Fundamentale Operation bei Baumabfragen mit Anwendungen in Computerbiologie (Artenevolution), Netzwerk-Routing und Versionskontrollsystemen. Verschiedene Algorithmen bieten unterschiedliche Zeit-Speicher-Kompromisse.
#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
Use 'null' for empty nodes
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
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← → StepR Reset1-4 Speed
Real-time Statistics
Algorithm Performance Metrics
Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
Steps
1/ 0
Algorithm Visualization
Step 1 of 0
Initialize array to begin
Default
Comparing
Swapped
Sorted
Code Execution
Currently executing
Previously executed
Implementation