在二叉搜索树中找到中位数 [英] Find median in binary search tree
问题描述
编写函数 T ComputeMedian() const
的实现,该函数在 O(n) 时间内计算树中的中值.假设树是 BST 但不一定是平衡的.回想一下,n 个数字的中位数定义如下:如果 n 是奇数,则中位数为 x,使得小于 x 的值的数量等于大于 x 的值的数量.如果 n 是偶数,则 1 加上小于 x 的值的数量等于大于 x 的值的数量.例如,给定数字 8、7、2、5、9,中位数为 7,因为有两个值小于 7,两个值大于 7.如果我们将数字 3 添加到集合中,中位数变为 5.
Write the implementation of the function T ComputeMedian() const
that computes the median value in the tree in O(n) time. Assume that the tree is a BST but is not necessarily balanced. Recall that the median of n numbers is defined as follows: If n is odd, the median is x such that the number of values smaller than x is equal to the number of values greater than x. If n is even, then one plus the number of values smaller than x is equal to the number of values greater than x. For example, given the numbers 8, 7, 2, 5, 9, the median is 7, because there are two values smaller than 7 and two values larger than 7. If we add number 3 to the set, the median becomes 5.
这里是二叉搜索树节点的类:
Here is the class of binary search tree node:
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>;
};
二叉搜索树类:
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) 个节点并返回它.我只是不知道怎么做.
I know I should count the nodes of the tree first and then do an inorder traversal until I reach (n/2)th node and return it. I just have no clue how.
推荐答案
正如你提到的,首先找到节点的数量,做任何遍历是相当容易的:
As you mentioned, it is fairly easy to first find the number of nodes, doing any traversal:
findNumNodes(node):
if node == null:
return 0
return findNumNodes(node.left) + findNumNodes(node.right) + 1
然后,当节点编号为 n/2 时,中序遍历会中止:
Then, with an inorder traversal that aborts when the node number is n/2:
// index is a global variable / class variable, or any other variable that is constant between all calls
index=0
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
个节点时,就返回它.
The idea is that in-order traversal processes nodes in BST in sorted manner. So, since the tree is a BST, the i
th node you process, is the i
th node in order, this is of course also true for i==n/2
, and when you find it is the n/2
th node, you return it.
作为旁注,您可以向 BST 添加功能以高效地查找 i
th 个元素(O(h)
,其中 h
是树的高度),使用顺序统计树.
As a side note, you can add functionality to BST to find i
th element efficiently (O(h)
, where h
is the tree's height), using order statistics trees.
这篇关于在二叉搜索树中找到中位数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!