Was ist Tri-Node Umstrukturierung von AVL-Bäumen?

Question

Ich habe ein wenig gegoogelt, aber nicht viel gefunden und nicht sicher, wo ich anfangen soll.

Sagen Sie bitte ein einfaches AVL Baum haben:

 2 
    /\ 
    1 3 

Sie wollen einen Knoten löschen und dann haben Sie AVL-Eigenschaft wiederherzustellen. Wenn gemeint ist, wie viel Tri-Node-Restrukturierung nach dem Löschen eines Wertes verursacht wird, was bedeuten sie?

Answer 1

Wenn ich mich richtig erinnere, wenn ein AVL-Baum aktualisiert wird, müssen in einigen Fällen verschiedene Rebalancing-Operationen durchgeführt werden, um den Invariant des Baumes zu erhalten, nämlich ein Suchbaum zu sein und ausgeglichen zu sein (mit einer Höhe, die logarithmisch begrenzt ist Anzahl der Knoten). Für die Entscheidung, welcher Rebalancing-Vorgang erforderlich ist, müssen bis zu drei Knoten berücksichtigt werden. Die Rotationsvorgänge sind in dieser Wikipedia article beschrieben. Das Beispiel, das Sie in Ihrer Frage angegeben haben, ist möglicherweise zu klein, um eine solche Operation erforderlich zu machen.