2015-05-01 27 views
5

Schreiben Sie die Implementierung der Funktion T ComputeMedian() const, die den Medianwert im Baum in O (n) Zeit berechnet. Angenommen, der Baum ist ein BST, ist aber nicht unbedingt ausgewogen. Erinnern wir uns, dass der Median von n Zahlen wie folgt definiert ist: Wenn n ungerade ist, ist der Median x, so dass die Anzahl der Werte kleiner als x gleich der Anzahl der Werte größer als x ist. Wenn n gerade ist, ist eins plus die Anzahl der Werte kleiner als x gleich der Anzahl der Werte größer als x. Bei den Zahlen 8, 7, 2, 5, 9 ist der Median beispielsweise 7, weil zwei Werte kleiner als 7 und zwei Werte größer als 7 sind. Wenn wir der Menge Nummer 3 hinzufügen, wird der Median 5. HierSuchen Sie den Median im binären Suchbaum

ist die Klasse von binären Suchbaum Knoten:

template <class T> 
class BSTNode 
{ 
public: 
BSTNode(T& val, BSTNode* left, BSTNode* right); 
~BSTNode(); 
T GetVal(); 
BSTNode* GetLeft(); 
BSTNode* GetRight(); 

private: 
T val; 
BSTNode* left; 
BSTNode* right; 
BSTNode* parent; //ONLY INSERT IS READY TO UPDATE THIS MEMBER DATA 
int depth, height; 
friend class BST<T>; 
}; 

Binary Suchbaum Klasse:

template <class T> 
class BST 
{ 
public: 
BST(); 
~BST(); 

bool Search(T& val); 
bool Search(T& val, BSTNode<T>* node); 
void Insert(T& val); 
bool DeleteNode(T& val); 

void BFT(void); 
void PreorderDFT(void); 
void PreorderDFT(BSTNode<T>* node); 
void PostorderDFT(BSTNode<T>* node); 
void InorderDFT(BSTNode<T>* node); 
void ComputeNodeDepths(void); 
void ComputeNodeHeights(void); 
bool IsEmpty(void); 
void Visit(BSTNode<T>* node); 
void Clear(void); 

private: 
BSTNode<T> *root; 
int depth; 
int count; 
BSTNode<T> *med; // I've added this member data. 

void DelSingle(BSTNode<T>*& ptr); 
void DelDoubleByCopying(BSTNode<T>* node); 
void ComputeDepth(BSTNode<T>* node, BSTNode<T>* parent); 
void ComputeHeight(BSTNode<T>* node); 
void Clear(BSTNode<T>* node); 

}; 

ich weiß, ich sollte die Knoten des Baumes zuerst zählen und dann ein inorder Traversal tun bis ich den (n/2) ten Knoten erreiche und ihn zurückgebe. Ich habe nur keine Ahnung wie.

+0

Im Fall einer Liste müssen Sie Zeiger an beiden Enden beginnen und nach innen arbeiten, um den Median zu finden. Da Ihr Baum jedoch nicht ausgeglichen ist, reduziert sich der Worst Case auf eine verkettete Liste. Daher können Sie nicht vermeiden, genau das gleiche zu tun. Beginne Zeiger mit den Min- und Max-Werten und berechne abwechselnd Inorder-Nachfolger (Min) und Inorder-Vorgänger (Max), bis die Werte gleich sind. – BadZen

+0

@BadZen Ich bin mit dem "inorder-Vorgänger" nicht ganz vertraut .. Könnten Sie bitte weiter erklären? –

+0

Next() und Prev() Baumwerte. – BadZen

Antwort

5

Wie Sie erwähnt hat, ist es ziemlich einfach, zuerst die Anzahl der Knoten zu finden, jede Traversal tun:

findNumNodes(node): 
    if node == null: 
     return 0 
    return findNumNodes(node.left) + findNumNodes(node.right) + 1 

Dann mit einem Inorder Traversal, das bricht, wenn die Knotennummer n/2 ist:

index=0 //id is a global variable/class variable, or any other variable that is constant between all calls 
findMedian(node): 
    if node == null: 
     return null 
    cand = findMedian(node.left) 
    if cand != null: 
     return cand 
    if index == n/2: 
     return node 
    index = index + 1 
    return findMedian(node.right) 

Die Idee ist, dass In-Order-Traversal Knoten in BST in sortierter Weise verarbeitet. Also, da der Baum eine BST ist, ist der i th-Knoten, den Sie verarbeiten, der i th-Knoten in der Reihenfolge, dies gilt natürlich auch für i==n/2, und wenn Sie es finden, ist der n/2 th Knoten, Sie es zurückgeben.


Als Randbemerkung, können Sie die Funktionalität von BST hinzufügen effizient i te Element zu finden (O(h), wo h die Höhe des Baumes ist), order statistics trees verwenden.

+0

danke für die Antwort, aber ich dachte schon darüber nach. Mein Problem ist, dass meine Funktion wie folgt aussehen sollte. 'T ComputeMedian() const ', wie Sie sehen können, hat es keine Parameter (Ich werde meinen Beitrag jetzt bearbeiten) Ist es möglich, es so zu tun? ' Vorlage T BST :: ComputeMedian() const { ComputeMedian (Wurzel); } ' Und ich implementiere' ComputeMedian (BSTNode * Knoten) 'genau wie du gesagt hast? Wird das immer noch ein O (n) sein? –

+0

@NataliAyoub Ja, Sie schließen es gerade mit konstanten Operationen ein. – amit

+0

Ich habe gerade meinen Post bearbeitet und den Code zusammen mit den Fehlern hinzugefügt. Könnten Sie das bitte überprüfen und mir sagen, was los ist? –

Verwandte Themen