Sortieren der Elemente in binären Bäumen

Question

Hier ist eine Frage, die ich kürzlich in einem Interview gestellt wurde. Ein Binärbaum wird mit einer Bedingung angegeben, dass jedes linke Kind 1 kleiner als Wurzel und das rechte Kind 1 größer ist. Hier ist ein Beispiel Baum

sortiert sie in O (1) und O (n) Zeitkomplexität.

Hier sind die Ansätze, die ich vorgeschlagen:

1. Verwenden Sie eine Zählung die Anzahl der einzelnen Elemente zu halten und dann wieder einmal ganz Traversal ist O getan (n) Zeit und O (n) Speicherkomplexität.
2. Lauflängencodierung verwenden. Bilden Sie eine Kette, wenn das Element mit der Zahl als Schlüssel wiederholt wird und als Wert zählt. Erfordert nur dann Platz zum Zählen, wenn nein wiederholt wird, und benötigt daher keinen zusätzlichen Speicherplatz außer Array, aber die Zeitkomplexität wird O (n log n) sein, da wir das Array durchqueren müssen, um zu sehen, ob es da ist.
3. Schließlich schlug ich breite erste Traversal. Wir benötigen O (log n) -Raum für die Warteschlangen- und O (n) -Zeitkomplexität (angenommen, dass die Einfügung eine O (1) -Linkliste ist).

Was sind Ihre Ansätze?

Answer 1

Fix einige Blattknoten des gegebenen Baum als NewHead zurückzukehren, um eine Liste statt Druck, eine nur erstellen und jede Show Anweisung zu ersetzen.

Schreiben Sie eine Funktion Pop() einige Knoten aus dem gegebenen Baum entfernen ..!

schreiben Pop-Knoten, so dass Sie es nur entfernen, wenn es ist! gleich NewHead.

Also Pop-Wert von Baum, fügen Sie es in den neuen binären Suchbaum mit New Head als Head-Knoten.

So wird u ein Element aus Baum hinzuzufügen, um neuen Suchbaum zu entfernen.

Bis Baum Kopf Punkt NewHead.

So alle Sie Elemente sind nun in binärer Suchbaum zeigt auf den neuen Kopf, der

offensichtlich in sortierter Reihenfolge sein wird.

So versprechen Sie eine Sortierung in O (NlogN).

Answer 2

Ich bekomme die Frage nicht. Sind binäre Bäume noch nicht sortiert? Wenn Sie aus den Einzelteilen, um drucken möchten (oder sie zugreifen, um), würde dieser Code arbeitet

/** 
* Show the contents of the BST in order 
*/ 
public void show() { 
show(root); 
System.out.println(); 
} 
private static void show(TreeNode node) { 
if (node == null) return; 
show(node.lchild); 
System.out.print(node.datum + " "); 
show(node.rchild); 
} 

Ich glaube, die o (n) Komplexität wäre. durch Zugabe des Kindes in die Liste

Answer 3

Schnellsortierung verwenden.

Die Knoten sind auf der untersten Ebene in mehreren Arrays sortiert & Diese Arrays von sortierten Elemente werden am Ende zusammengeführt.

z.

Funktion quick_sort (Knoten n)
1.Gehe in den linken Modus, wenn es nicht null ist, rufe quick_sort darauf auf.
2. Gehen Sie zu den richtigen Elementen, wenn nicht null, rufen Sie quick_sort darauf auf.
3. Ergebnisse der linken Knoten sortieren & rechten Knoten sortieren & aktuellen Knoten.
4. Zusammengeführtes Array zurückgeben.

Answer 4

Analyse

Ihre Definition eines binären Baum wir folgendes gegeben haben,

Jeder Knoten haben ein Elternteil, L-Kind, und R-Kind .. Wo:

L < N 

R > N 

P > N 

Wir können dies auch tun:

L < N AND R > N => L < N < R => L < R 

L < N AND P > N => L < N < P => L < P 

R > N AND P > N => N < MIN(P,R) 

N < MIN(P,R) AND L < N => L < N < MIN(P,R) 

Und das jetzt lassen Sie versuchen, es erweitert, N.L = Left-child of N:

N.L < N 
N.R > N 
N.P > N 

N.L.L < N.L < MIN(N, N.L.R) 
N.L.R > N.L > N.L.L 

N.R.L < N.R < MIN(N, N.R.R) 
N.R.R > N.R > N.R.L 

IF N IS N.P LEFT-CHILD: N < N.P < MIN(N.P.P, N.P.R) 

IF N IS N.P RIGHT-CHILD: N > N.P.R 

---

Lösungsvorschlag

Dieses Problem scheint komplex, aber meine Lösung wird Sortierung mittels fusionieren nach Werten in einer Traversierfolgeliste Einfügen von links- Right-Parent, das dem Zusammenführen helfen wird, eine Zeitkomplexität irgendwo zwischen seinem Durchschnitts- und Optimalfall zu erhalten, aber mit einem kleinen Trick, der die Vergleiche verwendet, die ich oben gemacht habe.

Zunächst sammeln wir Baumknoten in einer Liste, Links-Rechts-Elternteil-Traversal verwendet wird, angesichts der Tatsache, dass: N.L < N < MIN(N.R, N.P) und mit den Eltern ein höheres Gewicht zu geben unter der Annahme O(N.R) <= O(N.P) mit Werten linear abnehmen, wenn wir links-Seite jedes Mal gehen .. > N.R.R > N.R > N > N.L > N.L.L > .. .

Nach dem Sammeln der Baumknoten in dieser Traversierungsreihenfolge enthält die Liste einige sortierte Chunks, die die Merge-Sortierung unterstützen, die wir als nächstes verwenden werden.

Diese Lösung funktioniert in: Time = O(n log n + n), Space = O(n)

Hier wird der Algorithmus in Java (nicht getestet) geschrieben ist:

private class Node Comparable<Node> 
{ 
    public Node R; 
    public Node L; 
    public int value; 

    public Node (Node L, int val, Node R) 
    { 
     this.L = L; 
     this.value = val; 
     this.R = R; 
    } 

    @Override 
    public int compareTo(Node other) 
    { 
     return ((other != null) ? (this.value-other.value) : 0); 
    } 
} 

class Main 
{ 
    private static Node head; 

    private static void recursive_collect (Node n, ArrayList<Node> list) 
    { 
     if (n == null) return; 
     if (n.left != null) recursive_collect (n.L, list); 
     if (n.right != null) recursive_collect (n.R, list); 
     list.add(n.value); 
    } 

    public static ArrayList<Node> collect() 
    { 
     ArrayList<Node> list = new ArrayList<Node>(); 
     recursive_collect (head, list); 
     return list; 
    } 

    // sorting the tree: O(n log n + n) 
    public static ArrayList<Node> sortTree() 
    { 
     // Collecting nodes: O(n) 
     ArrayList<Node> list = collect(); 

     // Merge Sort: O(n log n) 
     Collections.sort(list); 

     return list; 
    } 

    // The example in the picture you provided 
    public static void createTestTree() 
    { 
     Node left1 = new Node (new Node(null,-2,null), -1, new Node(null,0,null)); 

     Node left2 = new Node (new Node(null,-1,null), 0, new Node(null,1,null)); 

     Node right = new Node (left2, 1, new Node(null,2,null)); 

     head = new Node (left1, 0, right); 
    } 

    // test 
    public static void main(String [] args) 
    { 
     createTestTree(); 

     ArrayList<Node> list = sortTree(); 

     for (Node n : list) 
     { 
      System.out.println(n.value); 
     } 
    } 
} 

Answer 5

Ich denke, Sie suchen DFS (Tiefensuche) . In der Tiefe-zuerst-Suche ist die Idee, so weit wie möglich von Nachbar zu Nachbar zu reisen, bevor Backtracking. Was bestimmt, wie tief möglich ist, ist, dass Sie Kanten folgen müssen, und Sie keine Spitze zweimal besuchen.

boost bereits bietet es: siehe here