Znajdź medianę w drzewie wyszukiwania binarnego

Question

Napisz implementację funkcji T ComputeMedian() const, która oblicza medianę w drzewie w czasie O (n). Załóżmy, że drzewo jest BST, ale niekoniecznie jest zrównoważone. Przypomnijmy, że mediana liczb n jest zdefiniowana następująco: jeśli n jest nieparzyste, medianą jest x takie, że liczba wartości mniejszych od x jest równa liczbie wartości większej niż x. Jeśli n jest parzyste, to jeden plus liczba wartości mniejszych od x jest równa liczbie wartości większej od x. Na przykład, biorąc pod uwagę liczby 8, 7, 2, 5, 9, mediana wynosi 7, ponieważ istnieją dwie wartości mniejsze niż 7 i dwie wartości większe niż 7. Jeśli dodamy do zestawu liczbę 3, mediana stanie się 5.

Oto klasa binarny węzła szukaj drzewa:

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 klasa wyszukiwania drzewo:

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); 

}; 

wiem, że powinienem liczyć węzły drzewa, a potem zrobić przechodzenie inorder aż osiągnę (n/2) węzeł i zwrócę go. Po prostu nie mam pojęcia jak.

Answer 1

Jak wspomniano, jest to dość łatwe do pierwszego znaleźć liczbę węzłów, robiąc żadnych przechodzenie:

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

Następnie z przechodzenia Inorder że przerywa gdy liczba węzłów jest n/2:

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) 

Pomysł polega na tym, że węzły procesów w systemie BST sortowane są w kolejności. Tak więc, ponieważ drzewo jest węzłem BST, węzeł, który przetwarzasz, jest i th węzeł w kolejności, to jest oczywiście prawdziwe także dla i==n/2, a gdy znajdziesz go w węźle n/2, zwrócisz go.

---

Na marginesie można dodać funkcjonalność BST znaleźć i ty element sprawnie (O(h), gdzie h jest wysokość drzewa'S), używając order statistics trees.