BaumalgorithmenAdvanced
AVL-Baum
Erster selbstbalancierender binarer Suchbaum, erfunden 1962 von Adelson-Velsky und Landis. Halt Hohenbalance durch Rotationen aufrecht und garantiert O(log n)-Operationen. Striktere Balancierung als Rot-Schwarz-Baume macht ihn ideal fur lookup-intensive Anwendungen wie Datenbanken und Dateisysteme.
#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
Watch rotations maintain balance!
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
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