Binary Search Tree Balance

Question

Ich arbeite an einer BST, die Knoten nach ihren Treffern und ihren Elementen ausgleichen wird, wobei ein Treffer ein Attribut ist, das zunimmt, wenn ein Knoten gefunden wird mit find(), contains() usw. Die Wurzel des Baums ist der Knoten mit der höchsten Anzahl von Treffern. Mein gesamter Code ist in Ordnung, außer der Balance-Methode, die den Baum ausbalanciert, nachdem ich einen Treffer erhöht habe. Ich benutze modifizierte AVL Tree rotieren Methoden (https://users.cs.fiu.edu/~weiss/dsj2/code/weiss/nonstandard/Rotations.java), wo ich nicht die Elemente, sondern die Treffer eines Knotens vergleichen. mein Code Ich kann es nicht egal zu arbeiten, was ich versuche, ich kann nicht der Baum richtig Hier Gleichgewicht erhalten, ist so weit:

public void balanceTree() { 
    balanceTree(root); 
} 

private void balanceTree(Node node) { 

    if (node.left.getHits() <= node.getHits() && node.right.getHits() <= node.getHits()) { 
     return; 
    } else if (node.left.getHits() > node.getHits()) { 
     node = rotateWithLeftChild(node); 

    } else if (node.right.getHits() > node.getHits()) { 
     node = rotateWithRightChild(node); 

    } 


} 

static Node rotateWithLeftChild(Node k2) { 
    Node k1 = k2.left; 
    k2.left = k1.right; 
    k1.right = k2; 
    return k1; 
} 

static Node rotateWithRightChild(Node k1) { 
    Node k2 = k1.right; 
    k1.right = k2.left; 
    k2.left = k1; 
    return k2; 
} 

Im Moment der Balance Methode löscht einfach den Knoten seiner sollte rotieren, ich habe versucht, es zu debuggen, konnte aber nicht sehen, was falsch ist.

Answer 1

In Java kann man nicht die übergebenen Parameter ändern, so dass man den neuen Knoten Wert zurückgeben muß.

public void balanceTree() { 
    root = balanceTree(root); 
} 

private Node balanceTree(Node node) 
    if (node.left.getHits() <= node.getHits() 
      && node.right.getHits() <= node.getHits()) { 
     node.left = balanceTree(node.left); 
     node.right = balanceTree(node.right); 
    } else if (node.left.getHits() > node.getHits()) { 
     node = rotateWithLeftChild(node); 
    } else if (node.right.getHits() > node.getHits()) { 
     node = rotateWithRightChild(node); 
    } 
    return node; 
} 

Vorausgesetzt, dass Sie den Baum nach jeder Einsatz Neuverteilung, dann braucht man nicht nach einer Drehung Rekursion den Teilbaum zu balancieren.

Ohne Rotation muss man rekursiv werden.

Der aktuelle Algorithmus rekursiert links und dann rechts, aber wenn links eine Rotation stattgefunden hat, kann der rechte Teilbaum nicht mehr rekursiv sein.

Besorgniserregender für diese Art von Modifikationsalgorithmen ist, dass sie sich möglicherweise nicht stabilisieren: das Gleichgewicht halten. Aber das werden Sie sicherlich beim Testen sehen.

Answer 2

Es gibt 2 Dinge, die mit diesem Code falsch sind.
1) Ich vermisse die Struktur dieses Baumes. Also müssen sie basierend auf ihrem hitCount sortiert werden, was im Grunde eine List/Collection ist, die nach hitCount sortiert ist?

Im Moment tauschen Sie Knoten mit ihrem linken und rechten Knoten aus, wenn sie einen höheren Trefferwert als sie selbst haben. Stellen Sie sich also 2 Knoten vor [A, B] A hat 1 hitCount und B hat 2 hitCounts. Also auf Sortierung (du propably itterate über den Knoten):
Situation Beginn: [A, B]

Erste Art: A hat eine geringere HitCount als B so Swap mit Recht. Ergebnis = [B, A]

Zweite Sortierung: A hat einen niedrigeren hitCount als B, also mit links tauschen. Ergebnis = [A, B]

Wo enden wir? Eine bessere Idee könnte sein, eine Liste zu verwenden und die Knoten basierend auf ihrem hitCount zu sortieren. Auf diese Weise musst du dich nicht mit all dem anlegen.

2) Ihre Tauschmethoden funktionieren nicht so, wie Sie denken. Schauen Sie genau hin:

static Node rotateWithLeftChild(Node k2) { 
    Node k1 = k2.left; 
    k2.left = k1.right; 
    k1.right = k2; 
    return k1; 
} 

// exact the same results: 
static Node rotateWithLeftChild(Node k2) 
{ 
    k2.left = k2; 
    return k2.left; 
} 

Scheint nicht richtig zu mir. Wahrscheinlich bedeutete Sie so etwas wie:

static Node rotateWithLeftChild(Node k2) 
{ 
    Node k1 = k2.left; 
    k1.right = k2.right; 
    k2.left = k1.left; 
    k1.left = k2; 
    k2.right = k1; 
    return k1; 
} 

Und natürlich das Gegenteil gilt für „rotateWithRightChild“.

Ich hoffe, dass dir das ein wenig geholfen hat.

Edit:

Wie man eine Liste/Sammlung für Ordnung implementieren? Sobald ein Knoten zum Baum hinzugefügt wurde, fügen Sie den Knoten einfach zu einer Lisf/Sammlung hinzu. Und wenn man die Knoten sortiert werden sollen, einfach verwenden:

//myNodesCollection is the List/Collection containing all the nodes. 
static void sortByHitCount() 
{ 
    Collections.sort(myNodesCollection, (n1, n2) -> n1.getHits() - n2.getHits()); 
} 

Es könnte kompliziert erscheinen, aber dies ist eine Methode, die Sortierung alles für Sie tun. Der erste Parameter ist die Liste/Sammlung, die Sie sortieren möchten. Der zweite Parameter ist ein Komparator, der in diesem Fall jeden Knoten basierend auf seinem hitCount vergleicht.

Dokumentation: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html