Trouver la médiane dans un arbre de recherche binaire

Écrire la mise en œuvre de la fonction T ComputeMedian() const qui calcule la valeur médiane de l'arbre en O(n) fois. Supposons que l'arbre est un BST, mais n'est pas nécessairement équilibré. Rappelons que la médiane de n nombres est définie comme suit: Si n est impair, la médiane est de x telle que le nombre de valeurs inférieures à x est égal au nombre de valeurs supérieures à x. Si n est pair, alors un plus le nombre de valeurs inférieures à x est égal au nombre de valeurs supérieures à x. Par exemple, étant donné le nombre 8, 7, 2, 5, 9, la médiane est de 7, parce qu'il y a deux valeurs inférieures à 7 et à deux les valeurs supérieures à 7. Si l'on ajoute le numéro 3 pour l'ensemble, la médiane devient 5.

Ici est la classe d'une recherche binaire nœud de l'arborescence:

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

Binaire de recherche, de classe de l'arbre:

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

};

Je sais que je devrais compter les noeuds de l'arbre en premier et ensuite faire un afinde traversée jusqu'à ce que j'ai à portée de main (n/2)ème nœud et le retourner. J'ai juste aucune idée de comment.

Dans le cas d'une liste, vous auriez à commencer pointeurs aux deux extrémités et de travailler vers l'intérieur pour trouver la médiane. Mais depuis votre arbre n'est pas équilibré, le pire des cas se réduit à une liste liée. À cet effet, vous ne peut pas éviter de faire exactement la même chose. Début des pointeurs sur les valeurs min et max, et alternativement calculer afinde-successeur(min) et afinde prédécesseur(max) jusqu'à ce que l'égalité.
Je ne suis pas assez familier avec le "afinde prédécesseur".. pouvez-vous m'expliquer de plus?
Next() et Prev() de l'arbre des valeurs.

OriginalL'auteur Natali Ayoub | 2015-05-01

  1. 5

    Comme vous l'avez mentionné, il est assez facile de d'abord trouver le nombre de nœuds, de faire toute la traversée:

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

    Ensuite, avec une afinde de la traversée qui s'interrompt lorsque le numéro de nœud est 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)

    L'idée est que dans l'ordre de la traversée des processus de nœuds dans le BST dans triés. Donc, puisque l'arbre est un BST, le ième nœud de processus, est le ième nœud dans l'ordre, bien sûr, cela est également vrai pour les i==n/2, et lorsque vous trouvez qu'il est le n/2ème nœud, vous le retourner.

    Comme une note de côté, vous pouvez ajouter des fonctionnalités à la STB pour trouver iélément th efficacement (O(h), où h est l'arbre de hauteur), à l'aide de les statistiques d'ordre arbres.

    merci pour la réponse, mais j'ai déjà pensé à cela. Mon problème est que ma fonction devrait ressembler à ceci T ComputeMedian() const donc, comme vous pouvez le voir, il n'a pas de paramètres (je vais éditer mon post aujourd'hui) Est-il possible de le faire de cette template <class T> T BST<T>::ComputeMedian() const { ComputeMedian(root); } Et j'en œuvre ComputeMedian(BSTNode<T>* node) juste comme vous l'avez dit? Sera-ce encore être un O(n)?
    Oui, vous êtes juste en l'enveloppant avec constante des opérations.
    Je viens d'édité mon post et ajouté le code avec les erreurs, pourriez-vous s'il vous plaît vérifier et me dire quel est le problème?
    Il est hors de portée de la question d'origine, vous devez revenir à la version précédente, et de poser une nouvelle question de la liaison de celle-ci et indiquant ce que vous avez fait depuis, et qu'est-ce que le nouveau problème que vous rencontrez.
    pas sûr que je suis lol je suis un peu nouveau ici >.<

    OriginalL'auteur amit