Die Splay Tree Rotation ist ein wichtiger Bestandteil der Splay-Baum-Datenstruktur, die dazu dient, häufig verwendete Elemente näher zur Wurzel zu bringen, um den Zugriff auf sie zu beschleunigen. Bei einer Splay-Operation wird ein Knoten, der als Ziel identifiziert wurde, durch eine Serie von Rotationen an die Wurzel des Baumes verschoben. Es gibt drei Hauptarten von Rotationen: Zig, Zig-Zig und Zig-Zag.
Zig: Tritt auf, wenn der Zielknoten ein Kind der Wurzel ist. Hierbei wird der Zielknoten zur neuen Wurzel, und der alte Wurzelknoten wird zum anderen Kind des neuen Wurzelknotens.
Zig-Zig: Tritt auf, wenn der Zielknoten ein Kind des linken (oder rechten) Kindes der Wurzel ist. In diesem Fall werden beide Knoten gleichzeitig rotiert, sodass der Zielknoten zur neuen Wurzel wird.
Zig-Zag: Tritt auf, wenn der Zielknoten ein Kind des rechten (oder linken) Kindes ist, aber nicht direkt des Wurzelknotens. Hier erfolgt eine Kombination von Rotationen, um den Zielknoten in die Nähe der Wurzel zu bringen.
Diese Rotationen sorgen dafür, dass die Zug
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.