在二叉搜索树中查找中位数

Question

在二叉搜索树中查找中位数

8

实现函数T ComputeMedian() const，以O(n)时间复杂度计算树中的中位数。假设树是BST（二叉搜索树），但不一定平衡。回想一下n个数字的中位数定义：如果n为奇数，则中位数为x，使得小于x的值的数量等于大于x的值的数量；如果n为偶数，则小于x的值的数量加上1等于大于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>;
};

二叉搜索树类：

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)个节点并返回它。但是我不知道该怎么做。

- Nat

在列表的情况下，您必须从两端开始指针并向内工作以找到中位数。但由于您的树不平衡，最坏情况会降至链表。因此，您无法避免完全相同的操作。从最小和最大值开始指针，并交替计算inorder-successor(min)和inorder-predecessor(max)，直到它们相等。 - BadZen

@BadZen 我对“中序前驱”不是很熟悉，请您能否进一步解释一下？ - Nat

Next() 和 Prev() 树值。 - BadZen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

正如你所提到的，首先找到节点数量是相当容易的，可以通过任何遍历方式实现：

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

然后，使用中序遍历，在节点编号为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个节点时，返回它。

作为一个附注，你可以通过使用有序统计树来高效地（O(h)，其中h是树的高度）查找BST中的第i个元素。