Java Challenge

9.3.7Lösung 7: Tree Rotate ()

Binärbäume, insbesondere binäre Suchbäume, können zu Listen degenerieren, wenn Werte etwa nur in aufsteigender oder absteigender Reihenfolge eingefügt werden. Einer Dysbalance lässt sich entgegenwirken, indem man Teile des Baums rotiert. Schreiben Sie je eine Methode BinaryTreeNode<T> rotateLeft(BinaryTreeNode<T>) und BinaryTreeNode<T> rotateRight(BinaryTreeNode<T>), die den Baum um den als Parameter übergebenen Knoten nach links bzw. rechts rotiert.

BeispielNachfolgend wird eine Rotation nach links und eine nach rechts visualisiert, wobei sich die balancierte Ausgangslage in der Mitte befindet:

Abbildung 9-10 Rotation ...