Найти медиану в дереве двоичного поиска

Question

Напишите реализацию функции T ComputeMedian() const, которая вычисляет медианное значение в дереве в O (n) времени. Предположим, что дерево является BST, но не обязательно сбалансировано. Напомним, что медиана n чисел определяется следующим образом: если n нечетно, медиана равна x, так что число значений, меньших x, равно числу значений больше x. Если n четно, то одно плюс число значений, меньших x, равно числу значений больше x. Например, с учетом чисел 8, 7, 2, 5, 9 медиана равна 7, так как существует два значения меньше 7 и два значения больше 7. Если мы добавим число 3 в набор, медиана станет 5.

Вот класс бинарного узла дерева поиска:

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 класс дерево поиска:

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

}; 

Я знаю, что я должен считать узлы дерева первого, а затем сделать заказовМои обход пока я не дойду до (n/2) -го узла и не верну его. Я просто понятия не имею.

Answer 1

Как уже упоминалось, это довольно легко сначала найти число узлов, делать какие-либо обхода:

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

Затем с заказовМои обходе, что Прерывает когда номер узла п/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) 

Идея состоит в том, что в порядке очереди обходных узлов в BST сортируется. Таким образом, поскольку дерево является BST, i-й узел, который вы обрабатываете, является i-м узлом в порядке, это, конечно, также верно для i==n/2, и когда вы обнаружите, что это n/2-й узел, вы его возвращаете.

---

В качестве примечания, вы можете добавить функциональность BST найти i й элемент эффективно (O(h), где h является высота дерева), используя order statistics trees.