Löschen von Knoten im binären Suchbaum
Bevor das Löschen von Knoten in einem binären Suchbaum eingeführt wird, erklärt dieser Abschnitt zuerst, wie man die minimalen und maximalen Werte findet und wie man die minimalen und maximalen Werte löscht.
Am Beispiel des Minimalwerts (der Maximalwert ist analog):
Codelogik zum Finden des minimalen Schlüsselwerts: rekursiv im linken Kindknoten abwärts suchen:
...
// Gibt den Knoten mit dem minimalen Schlüsselwert im binären Suchbaum mit Wurzel node zurück
private Node minimum(Node node){
if( node.left == null )
return node;
return minimum(node.left);
}
...
// Gibt den Knoten mit dem minimalen Schlüsselwert im binären Suchbaum mit Wurzel node zurück
private Node minimum(Node node){
if( node.left == null )
return node;
return minimum(node.left);
}
...
Um den minimalen Schlüsselwert in einem binären Suchbaum zu löschen: Wenn der Knoten keinen rechten Teilbaum hat, wird er direkt gelöscht; wenn ein rechter Teilbaum existiert, wie in der Abbildung gezeigt:
Löschen von Knoten 22: Er hat ein rechtes Kind, also ersetzt man Knoten 22 einfach durch Knoten 33 aus dem rechten Teilbaum.
Dieses Löschen des Minimalwerts wird im Code ausgedrückt:
...
// Entfernt den minimalen Knoten aus dem binären Suchbaum mit Wurzel node
// Gibt die Wurzel des neuen binären Suchbaums nach dem Entfernen des Knotens zurück
private Node removeMin(Node node){
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
...
// Entfernt den minimalen Knoten aus dem binären Suchbaum mit Wurzel node
// Gibt die Wurzel des neuen binären Suchbaums nach dem Entfernen des Knotens zurück
private Node removeMin(Node node){
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
...
Nun besprechen wir das Löschen von Knoten in einem binären Suchbaum, wobei die folgenden drei Fälle auftreten:
1, Löschen eines Knotens mit nur einem linken Kind, wie Knoten 58 in der folgenden Abbildung.
Löschen Sie Element 58, und lassen Sie den linken Teilbaum direkt die Position von 58 einnehmen; die Eigenschaften des gesamten binären Suchbaums bleiben unverändert.
2, Löschen eines Knotens mit nur einem rechten Kind, wie Knoten 58 in der folgenden Abbildung.
Löschen Sie Element 58, und lassen Sie den rechten Teilbaum direkt die Position von 58 einnehmen; die Eigenschaften des gesamten binären Suchbaums bleiben unverändert.
3, Löschen eines Knotens, der sowohl ein linkes als auch ein rechtes Kind hat, wie Knoten 58 in der folgenden Abbildung.
(1) Finden Sie den minimalen Wert im rechten Teilbaum, das ist Knoten 59.
(2) Knoten 59 ersetzt den zu löschenden Knoten 58.
Basierend auf den oben genannten Regeln lautet das zentrale Codebeispiel zum Löschen des Knotens mit Schlüsselwert key in dem binären Suchbaum mit Wurzel node:
Quellcode-Paket-Download:Herunterladen
src/example/binary/BSTRemove.java Datei-Code:
package example.binary;
import java.util.LinkedList;
/**
* Knotenlöschung im binären Suchbaum
*/
public class BSTRemove<Key extends Comparable<Key>, Value> {
// Die Knoten im Baum sind eine private Klasse; die Außenwelt muss die spezifische Implementierung der Knoten des binären Suchbaums nicht kennen.
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
public Node(Node node){
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
}
}
private Node root; // Wurzelknoten
private int count; // Anzahl der Knoten im Baum
// Konstruktor, erstellt standardmäßig einen leeren binären Suchbaum
public BSTRemove() {
root = null;
count = 0;
}
// Gibt die Anzahl der Knoten im binären Suchbaum zurück
public int size() {
return count;
}
// Gibt zurück, ob der binäre Suchbaum leer ist
public boolean isEmpty() {
return count == 0;
}
// Fügt ein neues Datenpaar (Schlüssel, Wert) in den binären Suchbaum ein
public void insert(Key key, Value value){
root = insert(root, key, value);
}
// Prüft, ob der Schlüssel im binären Suchbaum existiert
public boolean contain(Key key){
return contain(root, key);
}
// Durchsucht den binären Suchbaum nach dem Wert, der dem Schlüssel entspricht. Wenn der Wert nicht vorhanden ist, wird null zurückgegeben
public Value search(Key key){
return search( root , key );
}
// Preorder-Durchlauf des binären Suchbaums
public void preOrder(){
preOrder(root);
}
// Inorder-Durchlauf des binären Suchbaums
public void inOrder(){
inOrder(root);
}
// Postorder-Durchlauf des binären Suchbaums
public void postOrder(){
postOrder(root);
}
// Levelorder-Durchquerung des binären Suchbaums
public void levelOrder(){
// Wir verwenden LinkedList als unsere Warteschlange
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while( !q.isEmpty() ){
Node node = q.remove();
System.out.println(node.key);
if( node.left != null )
q.add( node.left );
if( node.right != null )
q.add( node.right );
}
}
// Finde den minimalen Schlüssel im binären Suchbaum
public Key minimum(){
assert count != 0;
Node minNode = minimum( root );
return minNode.key;
}
// Finde den maximalen Schlüssel im binären Suchbaum
public Key maximum(){
assert count != 0;
Node maxNode = maximum(root);
return maxNode.key;
}
// Lösche den Knoten mit dem minimalen Schlüssel aus dem binären Suchbaum
public void removeMin(){
if( root != null )
root = removeMin( root );
}
// Lösche den Knoten mit dem maximalen Schlüssel aus dem binären Suchbaum
public void removeMax(){
if( root != null )
root = removeMax( root );
}
// Lösche den Knoten mit dem Schlüsselwert key aus dem binären Suchbaum
public void remove(Key key){
root = remove(root, key);
}
//********************
//* Hilfsfunktionen für den binären Suchbaum
//********************
// Knoten (key, value) in den bei node verwurzelten binären Suchbaum einfügen, unter Verwendung eines rekursiven Algorithmus
// Gibt die Wurzel des binären Suchbaums nach dem Einfügen des neuen Knotens zurück
private Node insert(Node node, Key key, Value value){
if( node == null ){
count ++;
return new Node(key, value);
}
if( key.compareTo(node.key) == 0 )
node.value = value;
else if( key.compareTo(node.key) < 0 )
node.left = insert( node.left , key, value);
else // key > node->key
node.right = insert( node.right, key, value);
return node;
}
// Prüft, ob der bei node verwurzelte binäre Suchbaum einen Knoten mit Schlüsselwert key enthält, unter Verwendung eines rekursiven Algorithmus
private boolean contain(Node node, Key key){
if( node == null )
return false;
if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}
// Finde den Wert, der key im binären Suchbaum mit Wurzel node entspricht, rekursiver Algorithmus
// Gib NULL zurück, wenn der Wert nicht existiert
private Value search(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
// Führe eine Preorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
private void preOrder(Node node){
if( node != null ){
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
// Führe eine Inorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
private void inOrder(Node node){
if( node != null ){
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}
// Führe eine Postorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
private void postOrder(Node node){
if( node != null ){
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
}
// Gibt den Knoten mit dem minimalen Schlüsselwert im binären Suchbaum mit Wurzel node zurück
private Node minimum(Node node){
if( node.left == null )
return node;
return minimum(node.left);
}
// Gib den Knoten mit dem maximalen Schlüsselwert im binären Suchbaum mit Wurzel node zurück
private Node maximum(Node node){
if( node.right == null )
return node;
return maximum(node.right);
}
// Entfernt den minimalen Knoten aus dem binären Suchbaum mit Wurzel node
// Gibt die Wurzel des neuen binären Suchbaums nach dem Entfernen des Knotens zurück
private Node removeMin(Node node){
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// Entferne den maximalen Knoten aus dem binären Suchbaum mit Wurzel node
// Gibt die Wurzel des neuen binären Suchbaums nach dem Entfernen des Knotens zurück
private Node removeMax(Node node){
if( node.right == null ){
Node leftNode = node.left;
node.left = null;
count --;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
// Den Knoten mit Schlüsselwert key aus dem binären Suchbaum mit Wurzel node löschen, rekursiver Algorithmus
// Gibt die Wurzel des neuen binären Suchbaums nach dem Entfernen des Knotens zurück
Node remove(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) < 0 ){
node.left = remove( node.left , key );
return node;
}
else if( key.compareTo(node.key) > 0 ){
node.right = remove( node.right, key );
return node;
}
else{ // key == node->key
// Der Fall, in dem der linke Teilbaum des zu löschenden Knotens leer ist
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
// Der Fall, in dem der rechte Teilbaum des zu löschenden Knotens leer ist
if( node.right == null ){
Node leftNode = node.left;
node.left = null;
count--;
return leftNode;
}
// Der Fall, in dem sowohl der linke als auch der rechte Teilbaum des zu löschenden Knotens nicht leer sind
// Den kleinsten Knoten finden, der größer als der zu löschende Knoten ist, d. h. den minimalen Knoten im rechten Teilbaum des zu löschenden Knotens
// Den zu löschenden Knoten durch diesen Knoten ersetzen
Node successor = new Node(minimum(node.right));
count ++;
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
count --;
return successor;
}
}
}
import java.util.LinkedList;
/**
* Knotenlöschung im binären Suchbaum
*/
public class BSTRemove<Key extends Comparable<Key>, Value> {
// Die Knoten im Baum sind eine private Klasse; die Außenwelt muss die spezifische Implementierung der Knoten des binären Suchbaums nicht kennen.
private class Node {
private Key key;
private Value value;
private Node left, right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
public Node(Node node){
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
}
}
private Node root; // Wurzelknoten
private int count; // Anzahl der Knoten im Baum
// Konstruktor, erstellt standardmäßig einen leeren binären Suchbaum
public BSTRemove() {
root = null;
count = 0;
}
// Gibt die Anzahl der Knoten im binären Suchbaum zurück
public int size() {
return count;
}
// Gibt zurück, ob der binäre Suchbaum leer ist
public boolean isEmpty() {
return count == 0;
}
// Fügt ein neues Datenpaar (Schlüssel, Wert) in den binären Suchbaum ein
public void insert(Key key, Value value){
root = insert(root, key, value);
}
// Prüft, ob der Schlüssel im binären Suchbaum existiert
public boolean contain(Key key){
return contain(root, key);
}
// Durchsucht den binären Suchbaum nach dem Wert, der dem Schlüssel entspricht. Wenn der Wert nicht vorhanden ist, wird null zurückgegeben
public Value search(Key key){
return search( root , key );
}
// Preorder-Durchlauf des binären Suchbaums
public void preOrder(){
preOrder(root);
}
// Inorder-Durchlauf des binären Suchbaums
public void inOrder(){
inOrder(root);
}
// Postorder-Durchlauf des binären Suchbaums
public void postOrder(){
postOrder(root);
}
// Levelorder-Durchquerung des binären Suchbaums
public void levelOrder(){
// Wir verwenden LinkedList als unsere Warteschlange
LinkedList<Node> q = new LinkedList<Node>();
q.add(root);
while( !q.isEmpty() ){
Node node = q.remove();
System.out.println(node.key);
if( node.left != null )
q.add( node.left );
if( node.right != null )
q.add( node.right );
}
}
// Finde den minimalen Schlüssel im binären Suchbaum
public Key minimum(){
assert count != 0;
Node minNode = minimum( root );
return minNode.key;
}
// Finde den maximalen Schlüssel im binären Suchbaum
public Key maximum(){
assert count != 0;
Node maxNode = maximum(root);
return maxNode.key;
}
// Lösche den Knoten mit dem minimalen Schlüssel aus dem binären Suchbaum
public void removeMin(){
if( root != null )
root = removeMin( root );
}
// Lösche den Knoten mit dem maximalen Schlüssel aus dem binären Suchbaum
public void removeMax(){
if( root != null )
root = removeMax( root );
}
// Lösche den Knoten mit dem Schlüsselwert key aus dem binären Suchbaum
public void remove(Key key){
root = remove(root, key);
}
//********************
//* Hilfsfunktionen für den binären Suchbaum
//********************
// Knoten (key, value) in den bei node verwurzelten binären Suchbaum einfügen, unter Verwendung eines rekursiven Algorithmus
// Gibt die Wurzel des binären Suchbaums nach dem Einfügen des neuen Knotens zurück
private Node insert(Node node, Key key, Value value){
if( node == null ){
count ++;
return new Node(key, value);
}
if( key.compareTo(node.key) == 0 )
node.value = value;
else if( key.compareTo(node.key) < 0 )
node.left = insert( node.left , key, value);
else // key > node->key
node.right = insert( node.right, key, value);
return node;
}
// Prüft, ob der bei node verwurzelte binäre Suchbaum einen Knoten mit Schlüsselwert key enthält, unter Verwendung eines rekursiven Algorithmus
private boolean contain(Node node, Key key){
if( node == null )
return false;
if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}
// Finde den Wert, der key im binären Suchbaum mit Wurzel node entspricht, rekursiver Algorithmus
// Gib NULL zurück, wenn der Wert nicht existiert
private Value search(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
// Führe eine Preorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
private void preOrder(Node node){
if( node != null ){
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
}
// Führe eine Inorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
private void inOrder(Node node){
if( node != null ){
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
}
// Führe eine Postorder-Traversierung auf dem binären Suchbaum mit Wurzel node durch, rekursiver Algorithmus
private void postOrder(Node node){
if( node != null ){
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
}
// Gibt den Knoten mit dem minimalen Schlüsselwert im binären Suchbaum mit Wurzel node zurück
private Node minimum(Node node){
if( node.left == null )
return node;
return minimum(node.left);
}
// Gib den Knoten mit dem maximalen Schlüsselwert im binären Suchbaum mit Wurzel node zurück
private Node maximum(Node node){
if( node.right == null )
return node;
return maximum(node.right);
}
// Entfernt den minimalen Knoten aus dem binären Suchbaum mit Wurzel node
// Gibt die Wurzel des neuen binären Suchbaums nach dem Entfernen des Knotens zurück
private Node removeMin(Node node){
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// Entferne den maximalen Knoten aus dem binären Suchbaum mit Wurzel node
// Gibt die Wurzel des neuen binären Suchbaums nach dem Entfernen des Knotens zurück
private Node removeMax(Node node){
if( node.right == null ){
Node leftNode = node.left;
node.left = null;
count --;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
// Den Knoten mit Schlüsselwert key aus dem binären Suchbaum mit Wurzel node löschen, rekursiver Algorithmus
// Gibt die Wurzel des neuen binären Suchbaums nach dem Entfernen des Knotens zurück
Node remove(Node node, Key key){
if( node == null )
return null;
if( key.compareTo(node.key) < 0 ){
node.left = remove( node.left , key );
return node;
}
else if( key.compareTo(node.key) > 0 ){
node.right = remove( node.right, key );
return node;
}
else{ // key == node->key
// Der Fall, in dem der linke Teilbaum des zu löschenden Knotens leer ist
if( node.left == null ){
Node rightNode = node.right;
node.right = null;
count --;
return rightNode;
}
// Der Fall, in dem der rechte Teilbaum des zu löschenden Knotens leer ist
if( node.right == null ){
Node leftNode = node.left;
node.left = null;
count--;
return leftNode;
}
// Der Fall, in dem sowohl der linke als auch der rechte Teilbaum des zu löschenden Knotens nicht leer sind
// Den kleinsten Knoten finden, der größer als der zu löschende Knoten ist, d. h. den minimalen Knoten im rechten Teilbaum des zu löschenden Knotens
// Den zu löschenden Knoten durch diesen Knoten ersetzen
Node successor = new Node(minimum(node.right));
count ++;
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
count --;
return successor;
}
}
}