Tìm trung vị trong cây tìm kiếm nhị phân

Question

Viết cách triển khai hàm T ComputeMedian() const tính giá trị trung bình trong cây theo thời gian O (n). Giả sử rằng cây là BST nhưng không nhất thiết phải cân bằng. Nhớ lại rằng số trung bình của các số n được định nghĩa như sau: Nếu n là số lẻ, số trung bình là x sao cho số lượng các giá trị nhỏ hơn x bằng với số lượng các giá trị lớn hơn x. Nếu n là chẵn, thì một cộng với số giá trị nhỏ hơn x bằng với số giá trị lớn hơn x. Ví dụ, với các số 8, 7, 2, 5, 9, trung bình là 7, vì có hai giá trị nhỏ hơn 7 và hai giá trị lớn hơn 7. Nếu chúng ta thêm số 3 vào tập hợp, trung vị sẽ là 5.

đây là lớp nhị phân nút cây tìm kiếm:

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 lớp cây tìm kiếm:

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

}; 

tôi biết tôi nên tính các nút của cây đầu tiên và sau đó làm một traversal inorder cho đến khi tôi đạt đến nút (n/2) và trả lại. Tôi không có đầu mối nào.

Answer 1

Như bạn nói, nó là khá dễ dàng để đầu tiên tìm ra số nút, làm bất kỳ traversal:

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

Sau đó, với một traversal inorder rằng hủy bỏ khi số nút là 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) 

Ý tưởng là các quy trình truyền tải theo thứ tự trong BST theo cách được sắp xếp. Vì vậy, vì cây là một BST, nút thứmà bạn xử lý, là nút thứ nhất i thứ tự, điều này tất nhiên cũng đúng đối với i==n/2 và khi bạn tìm thấy nút đó là nút thứ n/2, bạn sẽ trả lại.

---

Như một mặt lưu ý, bạn có thể thêm chức năng cho BST để tìm nguyên tố thứ i hiệu quả (O(h), nơi h là chiều cao của cây), sử dụng order statistics trees.