Ordenació eficient usant un BST X48149

Fes un procediment

  template <typename T>
  void ordena(vector<T>& v);

que ordeni @v@ de petit a gran amb un algorisme d’ordenació eficient que utilitzi un BST per aconseguir-ho. Ha de tenir un cost quasi lineal en el cas mig. El tipus @T@ admet una relació d’ordre total, és a dir, tenim una operació de comparació $<$ entre valors de tipus @T@.

Es proporciona una classe $bst$ amb els mètodes constructor i destructor ja implementats.

Cal enviar a jutge.org la següent especificació de la classe $bst$ i la implementació dels mètodes addicionals que creguis convenients dins del mateix fitxer. En el mateix fitxer s’ha d’incloure el procediment $ordena$. Pots ampliar la classe $bst$ amb els mètodes públics i privats que necessitis per poder implementar l’ordenació eficient.

#include <iostream>
#include <vector>
using namespace std;
typedef unsigned int nat;

template <typename Clau>
class bst {

  public:
    // Constructora per defecte. Crea un BST buit.
    bst();

    // Destructora
    ~bst();

    // Aquí va l'especificació dels mètodes públics addicionals

  private:
    struct node {
      Clau _k;      // Clau
      node* _esq;   // fill esquerre
      node* _dret;  // fill dret
    };
    node *_arrel;

    static void esborra_nodes(node* m);

    // Aquí va l'especificació dels mètodes privats addicionals
};

// Aquí va la implementació dels mètodes públics i privats de bst

// Aquí va la implementació del procediment ordena

En els següents exemples, l’entrada consisteix en vàries línies cadascuna d’elles representant un vector: El nombre d’elements del vector seguit dels seus valors. La sortida mostra els elements de cada vector un cop ordenats.