Erhalten tatsächlichen Index während des Einfügens in einem BST

Question

Ich möchte eine BST erstellen, die beim Einfügen von Element wird den Index davon in einem perfekt ausgeglichenen Baum zurückgeben. Zum Beispiel (die Zahl in Klammern gibt tatsächlichen Index):

5(1) 
    /\ 
/ \ 
    3(2) 6(3) 
/
2(4) 

oder

1(1) 
\ 
    \ 
    2(3) 
    \ 
    \ 
     3(7) 

Im zweiten Beispiel können wir sehen, dass es kein linkes Kind des Elements 1, aber immer noch 2 Element ein Index von 3, wie es in einem perfekt ausgeglichenen Baum der Fall wäre.

Der Wurzelknoten beginnt mit 1.

Was ein effizienter Weg, um den Index Return on Insertion sein würde?

nun in Einfügung eines Elements in einem BST ist mein Code wie folgt:

Node newNode = new Node(id); 
if(root==null){ 
      root = newNode; 
      return 1; 
     } 

Node current = root; 
     Node parent = null; 
     while(true){ 
      parent = current; 
      if(id<current.data){     
       current = current.left; 
       if(current==null){ 
        parent.left = newNode; 
        return; 
       } 
      }else{ 

       current = current.right; 
       if(current==null){ 
        parent.right = newNode; 
        return; 
       } 
      } 
     } 

Ich bin nicht in der Lage zu verstehen, wie ich das Niveau halten soll, wird das Element in die Berechnung den Index eingefügt wird.

Die Anzahl der Elemente, die eingefügt werden können, ist maximal 3 * 10^5. Das Speichern in einem Array, um die Indizes zu erhalten, ist keine effektive Methode

Answer 1

Eine Lösung besteht darin, den Binärbaum als eindimensionales Array darzustellen. Dies ist bei Implementierungen von binären Heaps üblich.

Ihre Implementierung wäre nicht ausgeglichen wie ein Heap, aber Sie können die gleichen Konzepte verwenden, da Sie wissen, dass es auf jeder Ebene 2^i Leerzeichen (beginnend mit 0 für die Wurzel) in einer Binärdatei gibt Baum.

Ihre Implementierung müsste sich von Knoten mit linken und rechten Zeigern zu einem eindimensionalen Array des Datentyps ändern, den der Baum enthält (Integer in Ihrem Fall).

Sie den Baum durch die Berechnung Indizes navigieren können:

• Eltern des Knotens i: array [i/2]
• linke Kind des Knotens i: array [2i]
• rechte Kind des Knotens i: array [2i + 1]

Informationen erhalten von http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html