Wie man einen binären Baum in einen binären Suchbaum in-place umwandelt, d. H. Wir können keinen zusätzlichen Raum verwenden

Question

Wie man einen binären Baum in einen binären Suchbaum in-place umwandelt, d. H. Wir können keinen zusätzlichen Raum verwenden.

Answer 1

Man braucht nicht viel zu geben zu gehen, aber wenn die Anforderung ist, was ich denke, es ist, haben Sie ein binärer Baum bereits im Speicher erstellt und sitzen, aber nicht sortiert (so, wie Sie es möchten sortiert werden, sowieso).

Ich gehe davon aus, dass der Baumknoten aussieht

struct tree_node { 
    struct tree_node * left; 
    struct tree_node * right; 
    data_t data; 
}; 

Ich gehe davon aus, dass Sie C

lesen können, während wir einfach fragen, herumsitzen, warum dieser Baum jemals ohne erstellt wurde, das in sortierter Reihenfolge erstellt, die uns nicht gut tut, also werde ich es ignorieren und nur damit umgehen, es zu sortieren.

Die Anforderung, dass kein zusätzlicher Platz benötigt wird, ist ungerade. Vorübergehend wird es zusätzlichen Platz geben, wenn nur auf dem Stapel. Ich gehe davon aus, dass dies bedeutet, dass malloc oder etwas ähnliches aufgerufen wird und dass der resultierende Baum nicht mehr Speicher benötigt als der ursprüngliche unsortierte Baum.

Die erste und einfachste Lösung besteht darin, eine Vorbestellung des unsortierten Baums durchzuführen, wobei alle Knoten aus diesem Baum entfernt und eine sortierte Einfügung in einen neuen Baum vorgenommen wird. Dies ist O (n + n log (n)), das ist O (n log (n)).

Wenn dies nicht das ist, was sie wollen, und Sie müssen Rotationen und Sachen verwenden ..... das ist schrecklich!

Ich dachte, dass Sie dies tun könnten, indem Sie eine ungerade Version einer Heap-Sortierung tun, aber ich stieß auf Probleme. Eine andere Sache, die in den Sinn kam, die schrecklich langsam wäre, würde eine seltsame Version der Blase Art auf dem Baum tun.

Dafür wird jeder Knoten verglichen und möglicherweise mit jedem seiner direkten Kinder (und daher auch mit seinem Eltern) wiederholt, bis Sie den Baum durchlaufen und keine erforderlichen Swaps finden.Eine Shaker-Sortierung (Bubble-Sortierung, die von links nach rechts und von rechts nach links geht) würde am besten funktionieren, und nach dem ersten Durchlauf müssten Sie keine Teilbäume mehr durchlaufen, die in Bezug auf das übergeordnete Element nicht in Ordnung waren .

Ich bin sicher, dass entweder dieser Algorithmus von jemand anderem vor mir ausgedacht wurde und einen coolen Namen hat, den ich einfach nicht kenne, oder dass er auf irgendeine Weise grundlegend fehlerhaft ist, was ich nicht sehe.

Die Berechnung der Laufzeit für den zweiten Vorschlag ist ziemlich kompliziert. Zuerst dachte ich, dass es einfach O (n^2) wäre, wie Bubble und Shaker, aber ich kann mich nicht davon überzeugen, dass die Subtree-Traversalvermeidung nicht genug gewinnt, um es ein bisschen besser zu machen als O (n^2). Im Wesentlichen erhalten Bubble- und Shaker-Sortierungen diese Optimierung auch, aber nur an den Enden, an denen die gesamte Sortierung früh auftritt und Sie die Grenzen reduzieren können. Mit dieser Baumversion haben Sie die Möglichkeit, auch Chunks in der Mitte des Sets zu vermeiden. Nun, wie ich schon sagte, es ist wahrscheinlich tödlich fehlerhaft.

Answer 2

Ein Binärbaum in der Regel ist ein binärer Suchbaum, in dem Fall keine Konvertierung erforderlich ist.

Vielleicht müssen Sie die Struktur von dem, von dem Sie konvertieren, klären. Ist der Quellbaum nicht ausgewogen? Ist es nicht nach dem Schlüssel geordnet, nach dem Sie suchen möchten? Wie bist du zum Quellenbaum gekommen?

Answer 3

Nun, wenn dies eine Interviewfrage ist, ist das erste, was ich herausplatzen würde (mit null tatsächlichen Gedanken): iteriere das gesamte Binary rekursiv und finde das kleinste Element. Nimm es aus dem Binärbaum. Wiederholen Sie nun den Prozess, bei dem Sie den gesamten Baum iterieren und das kleinste Element suchen und es als übergeordnetes Element des letzten gefundenen Elements hinzufügen (wobei das vorherige Element zum linken Kind des neuen Knotens wird). Wiederholen Sie so oft wie nötig, bis der ursprüngliche Baum leer ist. Am Ende bleibt der schlechteste sortierte Binärbaum - eine verkettete Liste. Ihr Zeiger zeigt auf den Stammknoten, der das größte Element ist.

Dies ist ein schrecklicher Algorithmus all-around - O (n^2) Laufzeit mit der schlechtesten möglichen binären Baum ausgegeben, aber es ist ein anständigen Ausgangspunkt, bevor besser mit etwas kommen und hat den Vorteil, Sie in der Lage, schreibe den Code dafür in etwa 20 Zeilen auf einem Whiteboard.

Answer 4

Inorder-Traversierung des Binärbaums durchführen und Ergebnis speichern. Sortieren Sie das Ergebnis in der richtigen Reihenfolge Bilden Sie den binären Suchbaum, indem Sie das mittlere Element der sortierten Liste als root verwenden (dies kann mit der binären Suche erfolgen). So erhalten wir einen ausgeglichenen binären Suchbaum.

Answer 5

Führen Sie den folgenden Algorithmus aus, um die Lösung zu erreichen.

1) finden Sie den Nachfolger in der Reihenfolge ohne Platz zu verwenden.

Node InOrderSuccessor(Node node) 
{ 
    if (node.right() != null) 
    { 
     node = node.right() 
     while (node.left() != null) 
      node = node.left() 
     return node 
    } 
    else 
    { 
     parent = node.getParent(); 
     while (parent != null && parent.right() == node) 
     { 
      node = parent 
      parent = node.getParent() 
     } 
     return parent 
    } 
} 

2) Sie um Traversal ohne Leerzeichen zu verwenden.

a) Finden Sie den ersten Knoten von inorder traversal. Es sollte das meiste Kind des Baumes verlassen haben, wenn es das linke oder rechte Kind hat, oder das rechte Kind selbst. b) Verwenden Sie den obigen Algorithmus, um den Nachfolger des ersten Knotens herauszufinden. c) Wiederholen Sie Schritt 2 für alle zurückgegebenen Nachfolger.

Verwenden Sie den obigen 2-Algorithmus, und führen Sie das Traversieren in Binärbaum durch, ohne zusätzlichen Speicherplatz zu verwenden. Bilden Sie den binären Suchbaum, wenn Sie eine Traversierung durchführen. Aber die Komplexität ist O(N2) Worst Case.

Answer 6

Haufen Art der Baum .. nlogn Komplexität ..

Answer 7

die Nachordnungsdurchquerung Sie und dass ein binärer Suchbaum erstellen.

struct Node * newroot = '\0'; 

struct Node* PostOrder(Struct Node* root) 
{ 
     if(root != '\0') 
     { 
      PostOrder(root->left); 
      PostOrder(root->right); 
      insertBST(root, &newroot); 
     } 
} 

insertBST(struct Node* node, struct Node** root) 
{ 
    struct Node * temp, *temp1; 
    if(root == '\0') 
    { 
     *root == node; 
     node->left == '\0'; 
     node->right == '\0'; 
    } 
    else 
    { 
     temp = *root; 
     while(temp != '\0') 
     { 
      temp1= temp; 
      if(temp->data > node->data) 
       temp = temp->left; 
      else 
       temp = temp->right; 
     } 
     if(temp1->data > node->data) 
     { 
      temp1->left = node; 
     } 
     else 
     { 
      temp1->right = node; 
     } 
     node->left = node->right = '\0'; 
    } 
} 

Answer 8

konvertieren Binary Tree zu einem doppelt verknüpften Listen- Inplace in O (n)
getan werden kann Dann sortieren sie sortieren mit verschmelzen, nlogn
die Liste an einen Baum Konvertieren zurück - O (n)

Einfache nlogn Lösung.

Answer 9

#include <stdio.h> 
#include <stdlib.h> 

typedef int data_t; 

struct tree_node { 
    struct tree_node * left; 
    struct tree_node * right; 
    data_t data; 
}; 

     /* a bonsai-tree for testing */ 
struct tree_node nodes[10] = 
{{ nodes+1, nodes+2, 1} 
,{ nodes+3, nodes+4, 2} 
,{ nodes+5, nodes+6, 3} 
,{ nodes+7, nodes+8, 4} 
,{ nodes+9, NULL, 5} 
,{ NULL, NULL, 6} 
,{ NULL, NULL, 7} 
,{ NULL, NULL, 8} 
,{ NULL, NULL, 9} 
     }; 

struct tree_node * harvest(struct tree_node **hnd) 
{ 
struct tree_node *ret; 

while (ret = *hnd) { 
     if (!ret->left && !ret->right) { 
       *hnd = NULL; 
       return ret; 
       } 
     if (!ret->left) { 
       *hnd = ret->right; 
       ret->right = NULL;; 
       return ret; 
       } 
     if (!ret->right) { 
       *hnd = ret->left; 
       ret->left = NULL;; 
       return ret; 
       } 
     hnd = (rand() &1) ? &ret->left : &ret->right; 
     } 

return NULL; 
} 

void insert(struct tree_node **hnd, struct tree_node *this) 
{ 
struct tree_node *ret; 

while ((ret= *hnd)) { 
     hnd = (this->data < ret->data) ? &ret->left : &ret->right; 
     } 
*hnd = this; 
} 

void show(struct tree_node *ptr, int indent) 
{ 
if (!ptr) { printf("Null\n"); return; } 

printf("Node(%d):\n", ptr->data); 
printf("%*c=", indent, 'L'); show (ptr->left, indent+2); 
printf("%*c=", indent, 'R'); show (ptr->right, indent+2); 
} 

int main(void) 
{ 
struct tree_node *root, *this, *new=NULL; 

for (root = &nodes[0]; this = harvest (&root); ) { 
     insert (&new, this); 
     } 

show (new, 0); 
return 0; 
} 

Answer 10

struct Node 
{ 
    int value; 
    Node* left; 
    Node* right; 
}; 

void swap(int& l, int& r) 
{ 
    int t = l; 
    l = r; 
    r = t; 
} 

void ConvertToBST(Node* n, Node** max) 
{ 
    if (!n) return; 

    // leaf node 
    if (!n->left && !n->right) 
    { 
     *max = n; 
     return; 
    } 

    Node *lmax = NULL, *rmax = NULL; 
    ConvertToBST(n->left, &lmax); 
    ConvertToBST(n->right, &rmax); 

    bool swapped = false; 
    if (lmax && n->value < lmax->value) 
    { 
     swap(n->value, lmax->value); 
     swapped = true; 
    } 

    if (rmax && n->value > rmax->value) 
    { 
     swap(n->value, n->right->value); 
     swapped = true; 
    } 

    *max = n; 
    if (rmax && rmax->value > n->value) *max = rmax; 

    // If either the left subtree or the right subtree has changed, convert the tree to BST again 
    if (swapped) ConvertToBST(n, max); 
}