Créer un arbre de recherche binaire équilibré à partir D'une liste de liens triés

vous ne pouvez pas faire mieux que le temps linéaire, puisque vous devez au moins lire tous les éléments de la liste, donc vous pourriez aussi bien Copier la liste dans un tableau (temps linéaire) et ensuite construire l'arbre efficacement de la manière habituelle, i.e. si vous aviez la liste [9,12,18,23,24,51,84], alors vous commenceriez par faire 23 la racine, avec les enfants 12 et 51, puis 9 et 18 devenir enfants de 12, et 24 et 84 devenir enfants de 51. Dans l'ensemble, devrait être O(n) Si vous le faites bien.

Le réel algorithme, pour ce que cela vaut, est "prendre l'élément central de la liste comme la racine, et recursivement construire BSTs pour les sous-listes à la gauche et à droite de l'élément central et les attacher sous la racine".

Le Meilleur n'est pas seulement une question de temps de course asynmptopique. La liste des liens triés contient toutes les informations nécessaires pour créer directement l'arbre binaire, et je pense que c'est probablement ce qu'ils recherchent

notez que la première et la troisième entrées deviennent des enfants de la deuxième, puis le quatrième noeud a des enfants de la deuxième et de la sixième (qui a des enfants de la cinquième et de la septième) et ainsi de suite...

en code psuedo

read three elements, make a node from them, mark as level 1, push on stack
loop
    read three elemeents and make a node of them
    mark as level 1
    push on stack
    loop while top two enties on stack have same level (n)
         make node of top two entries, mark as level n + 1, push on stack
while elements remain in list

(avec un peu de réglage pour quand il reste moins de trois éléments ou un arbre déséquilibré à tout moment)

EDIT:

en tout point, il y a un noeud gauche de hauteur N sur la pile. L'étape suivante consiste à lire un élément, puis à lire et à construire un autre noeud de hauteur N sur la pile. Pour construire un noeud de hauteur N, faire et pousser un noeud de hauteur n -1 sur la pile, puis lire un élément, faire un autre noeud de hauteur N-1 sur la pile -- qui est un appel récursif.

en fait, cela signifie l'algorithme (même modifié) ne produira pas un arbre équilibré. S'il y a 2n+1 noeuds, il produira un arbre avec 2N-1 valeurs à gauche, et 1 à droite.

donc je pense que la réponse de @sgolodetz est meilleure, à moins que je puisse penser à un moyen de rééquilibrer l'arbre comme il est construit.

question piège!

la meilleure façon est d'utiliser le STL, et vous profitez du fait que le conteneur associatif trié ADT, dont l'ensemble est une mise en œuvre, exige l'insertion de gammes triées ont amorti le temps linéaire. Tout ensemble de données de base satisfaisant pour une langue devrait offrir une garantie similaire. Pour une vraie réponse, voir les solutions tout à fait intelligentes d'autres ont fourni.

c'est Quoi? Je devrait offrir quelque chose d'utile?

Hum...

Que Diriez-vous de ceci?

le plus petit arbre significatif possible dans un arbre binaire équilibré est de 3 noeuds. Une mère et ses deux enfants. Le premier exemple d'un tel arbre est le premier de trois éléments. Enfant-parent-enfant. Imaginons maintenant ceci comme un seul noeud. Bon, eh bien, nous n'avons plus un arbre. Mais nous savons que la forme que nous voulons, c'est Enfant-parent-enfant.

Fait pour un moment avec nos imaginations, nous voulons garder un pointeur vers le parent dans cette première triumvirat. Mais c'est individuellement liée!

On veut quatre pointeurs, que j'appellerai A, B, C, et D. Donc, on déplace A à 1, b est égal à A et on avance à 1. Mettez C égal à B, et avancez de deux. Le noeud sous B indique déjà son droit à l'enfant. Nous construisons notre arbre initial. On laisse B au parent de Tree one. C est assis à la noeud qui aura nos deux arbres minimaux comme enfants. Mettez a égal à C, et avancez-en un. Mettez D égal à A, et avancez-en un. Nous pouvons maintenant construire notre prochain arbre minimal. D pointe à la racine de cet arbre, B pointe à la racine de l'autre, et C pointe à la... la nouvelle racine à partir de laquelle nous accrocherons nos deux arbres minimaux.

Que Diriez-vous de quelques photos?

[A][B][-][C]  

avec notre image d'un arbre minimal comme noeud...

[B = Tree][C][A][D][-]

Et puis

[Tree A][C][Tree B]

sauf qu'on a un problème. Le noeud deux après D est notre prochaine racine.

[B = Tree A][C][A][D][-][Roooooot?!]  

Il serait beaucoup plus facile pour nous si nous pouvions simplement maintenir un pointeur à la place de et C. s'avère, puisque nous savons qu'il sera le point de C, nous pouvons aller de l'avant et de commencer la construction du nœud dans l'arbre binaire qui va le tenir, et dans ce cadre, nous pouvons entrer C en elle-gauche nœud. Comment Pouvons-nous faire cela avec élégance?

Définir le pointeur du Nœud sous C au noeud sous B.

C'est tromper dans tous les sens du terme, mais en utilisant ce truc, on libère B.

Alternativement, vous pouvez être sain d'esprit, et en fait commencer à construire la structure de noeud. Après tout, vous ne pouvez vraiment pas réutiliser les noeuds de la SLL, ils sont probablement pod structs.

alors maintenant...

[TreeA]<-[C][A][D][-][B]  
[TreeA]<-[C]->[TreeB][B] 

Et... Attends une seconde. Nous pouvons utiliser ce même truc pour libérer C, si nous nous laissons simplement penser que c'est seul un nœud d'un arbre. Parce qu'après tout, ce n'est vraiment qu'un seul noeud.

[TreeC]<-[B][A][D][-][C]  

Nous pouvons généraliser nos astuces.

[TreeC]<-[B][TreeD]<-[C][-]<-[D][-][A]    
[TreeC]<-[B][TreeD]<-[C]->[TreeE][A]  
[TreeC]<-[B]->[TreeF][A]  
[TreeG]<-[A][B][C][-][D]
[TreeG]<-[A][-]<-[C][-][D]  
[TreeG]<-[A][TreeH]<-[D][B][C][-]  
[TreeG]<-[A][TreeH]<-[D][-]<-[C][-][B]  
[TreeG]<-[A][TreeJ]<-[B][-]<-[C][-][D]  
[TreeG]<-[A][TreeJ]<-[B][TreeK]<-[D][-]<-[C][-]      
[TreeG]<-[A][TreeJ]<-[B][TreeK]<-[D][-]<-[C][-]  

il manque une étape cruciale!

[TreeG]<-[A]->([TreeJ]<-[B]->([TreeK]<-[D][-]<-[C][-]))  

Devient :

[TreeG]<-[A]->[TreeL->([TreeK]<-[D][-]<-[C][-])][B]    
[TreeG]<-[A]->[TreeL->([TreeK]<-[D]->[TreeM])][B]  
[TreeG]<-[A]->[TreeL->[TreeN]][B]  
[TreeG]<-[A]->[TreeO][B]  
[TreeP]<-[B]  

évidemment, l'algorithme peut être nettoyé considérablement, mais j'ai pensé qu'il serait intéressant de démontrer comment on peut optimiser au fur et à mesure en concevant itérativement votre algorithme. Je pense que c' le type de processus est ce qu'un bon employeur devrait chercher plus que tout autre.

le truc, en gros, c'est que chaque fois que nous atteignons le point médian suivant, dont nous savons qu'il s'agit d'un futur parent, nous savons que son sous-arbre gauche est déjà terminé. L'autre truc, c'est que nous en avons fini avec un noeud une fois qu'il a deux enfants et quelque chose qui le pointe, même si tous les sous-arbres ne sont pas finis. En utilisant ceci, nous pouvons obtenir ce que je suis à peu près sûr est une solution de temps linéaire, comme chaque élément est touché seulement 4 fois au plus. Le problème est que cela dépend d'être donné une liste qui formera un arbre de recherche binaire vraiment équilibré. Il y a, en d'autres termes, des contraintes cachées qui peuvent rendre cette solution soit beaucoup plus difficile à appliquer, soit impossible. Par exemple, si vous avez un nombre impair d'éléments, ou s'il y a beaucoup de valeurs non uniques, cela commence à produire un arbre assez stupide.

Considérations:

• Rendre l' élément unique.
• insérez un élément factice à la fin si le nombre de noeuds est impair.
• aspirant singulièrement à une mise en œuvre plus naïve.
• utilisez une déque pour garder les racines des sous-arbres terminés et les points médians dans, au lieu de mucking autour avec mon deuxième tour.

Ceci est une implémentation python:

def sll_to_bbst(sll, start, end):
    """Build a balanced binary search tree from sorted linked list.

    This assumes that you have a class BinarySearchTree, with properties
    'l_child' and 'r_child'.

    Params:
        sll: sorted linked list, any data structure with 'popleft()' method,
            which removes and returns the leftmost element of the list. The
            easiest thing to do is to use 'collections.deque' for the sorted
            list.
        start: int, start index, on initial call set to 0
        end: int, on initial call should be set to len(sll)

    Returns:
        A balanced instance of BinarySearchTree

    This is a python implementation of solution found here: 
    http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

    """

    if start >= end:
        return None

    middle = (start + end) // 2
    l_child = sll_to_bbst(sll, start, middle)
    root = BinarySearchTree(sll.popleft())
    root.l_child = l_child
    root.r_child = sll_to_bbst(sll, middle+1, end)

    return root

au lieu de la liste des liens triés, on m'a demandé sur un tableau trié (cela n'a pas d'importance bien que logiquement, mais oui le temps d'exécution varie) de créer un BST DE hauteur minimale, voici le code que je pourrais sortir:

typedef struct Node{
     struct Node *left;
     int info;
     struct Node  *right;
}Node_t;

Node_t* Bin(int low, int high) {

     Node_t* node = NULL;
     int mid = 0;

     if(low <= high) {
         mid = (low+high)/2;
         node = CreateNode(a[mid]);
         printf("DEBUG: creating node for %d\n", a[mid]);

        if(node->left == NULL) {
            node->left = Bin(low, mid-1);
        }

        if(node->right == NULL) {
            node->right = Bin(mid+1, high);
        }

        return node;
    }//if(low <=high)
    else {
        return NULL;
    }
}//Bin(low,high)


Node_t* CreateNode(int info) {

    Node_t* node = malloc(sizeof(Node_t));
    memset(node, 0, sizeof(Node_t));
    node->info = info;
    node->left = NULL;
    node->right = NULL;

    return node;

}//CreateNode(info)

// call function for an array example: 6 7 8 9 10 11 12, it gets you desired 
// result

 Bin(0,6); 

HTH Somebody..

voici le pseudo algorithme récursif que je vais suggérer.

createTree(treenode *root, linknode *start, linknode *end)
{
   if(start == end or start = end->next)
   {
      return; 
   } 
   ptrsingle=start;
   ptrdouble=start;
   while(ptrdouble != end and ptrdouble->next !=end)
   {
    ptrsignle=ptrsingle->next;
    ptrdouble=ptrdouble->next->next;
   }
   //ptrsignle will now be at the middle element. 
   treenode cur_node=Allocatememory;
   cur_node->data = ptrsingle->data;
   if(root = null)
       {
           root = cur_node; 
       }
   else
      {
         if(cur_node->data (less than) root->data)
          root->left=cur_node
         else
           root->right=cur_node
      }
   createTree(cur_node, start, ptrSingle);
   createTree(cur_node, ptrSingle, End); 
}

Racine = null; Le premier appel sera createtree(Racine, liste, null);

nous faisons la construction récursive de l'arbre, mais sans utiliser le tableau intermédiaire. Pour obtenir le milieu de l'élément chaque fois que nous avançons deux pointeurs, l'un par un élément, d'autres par deux éléments. Au moment où le deuxième pointeur est à la fin, le premier pointeur sera au milieu.

Le le temps de fonctionnement sera o (nlogn). L'espace supplémentaire sera o(logn). Pas une solution efficace pour une situation réelle où vous pouvez avoir arbre R-B qui garantit l'insertion nlogn. Mais assez bon pour un entretien.

dans la réponse de @Stuart, le tableau qu'il a présenté est la structure de données de soutien pour le BST. L'opération find par exemple n'aurait besoin que d'effectuer des calculs de tableaux d'index pour traverser l'arbre. La croissance du tableau et la suppression des éléments seraient la partie la plus délicate, donc je préférerais un vecteur ou une autre structure de recherche de données à temps constant.

la réponse de Jake aussi utilise ce fait mais nécessite malheureusement de parcourir la liste pour trouver à chaque fois pour faire une opération get(index). Mais ne nécessite aucune utilisation de mémoire supplémentaire.

à moins que l'intervieweur n'ait expressément mentionné qu'ils voulaient une représentation de la structure de l'arbre, j'utiliserais la réponse de @Stuart.

dans une question comme celle-ci, on vous donnerait des points supplémentaires pour discuter des compromis et de toutes les options que vous avez.

espérons que l'explication détaillée sur ce post aide: http://preparefortechinterview.blogspot.com/2013/10/planting-trees_1.html

une mise en oeuvre légèrement améliorée de @1337c0d3r dans mon blog.

// create a balanced BST using @len elements starting from @head & move @head forward by @len
TreeNode *sortedListToBSTHelper(ListNode *&head, int len) {
    if (0 == len)   return NULL;

    auto left = sortedListToBSTHelper(head, len / 2);
    auto root = new TreeNode(head->val);
    root->left = left;
    head = head->next;
    root->right = sortedListToBSTHelper(head, (len - 1) / 2);
    return root;
}

TreeNode *sortedListToBST(ListNode *head) {
    int n = length(head);
    return sortedListToBSTHelper(head, n);
}

si vous savez combien de noeuds sont dans la liste liée, vous pouvez le faire comme ceci:

// Gives path to subtree being built.  If branch[N] is false, branch
// less from the node at depth N, if true branch greater.
bool branch[max depth];

// If rem[N] is true, then for the current subtree at depth N, it's
// greater subtree has one more node than it's less subtree.
bool rem[max depth];

// Depth of root node of current subtree.
unsigned depth = 0;

// Number of nodes in current subtree.
unsigned num_sub = Number of nodes in linked list;

// The algorithm relies on a stack of nodes whose less subtree has
// been built, but whose right subtree has not yet been built.  The
// stack is implemented as linked list.  The nodes are linked
// together by having the "greater" handle of a node set to the
// next node in the list.  "less_parent" is the handle of the first
// node in the list.
Node *less_parent = nullptr;

// h is root of current subtree, child is one of its children.
Node *h, *child;

Node *p = head of the sorted linked list of nodes;

LOOP // loop unconditionally

    LOOP WHILE (num_sub > 2)
        // Subtract one for root of subtree.
        num_sub = num_sub - 1;

        rem[depth] = !!(num_sub & 1); // true if num_sub is an odd number
        branch[depth] = false;
        depth = depth + 1;
        num_sub = num_sub / 2;
    END LOOP

    IF (num_sub == 2)
        // Build a subtree with two nodes, slanting to greater.
        // I arbitrarily chose to always have the extra node in the
        // greater subtree when there is an odd number of nodes to
        // split between the two subtrees.

        h = p;
        p = the node after p in the linked list;
        child = p;
        p = the node after p in the linked list;
        make h and p into a two-element AVL tree;
    ELSE  // num_sub == 1

        // Build a subtree with one node.

        h = p;
        p = the next node in the linked list;
        make h into a leaf node;
    END IF

    LOOP WHILE (depth > 0)
        depth = depth - 1;
        IF (not branch[depth])
            // We've completed a less subtree, exit while loop.
            EXIT LOOP;
        END IF

        // We've completed a greater subtree, so attach it to
        // its parent (that is less than it).  We pop the parent
        // off the stack of less parents.
        child = h;
        h = less_parent;
        less_parent = h->greater_child;
        h->greater_child = child;
        num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1;
        IF (num_sub & (num_sub - 1))
          // num_sub is not a power of 2
          h->balance_factor = 0;
        ELSE
          // num_sub is a power of 2
          h->balance_factor = 1;
        END IF
    END LOOP

    IF (num_sub == number of node in original linked list)
        // We've completed the full tree, exit outer unconditional loop
        EXIT LOOP;
    END IF

    // The subtree we've completed is the less subtree of the
    // next node in the sequence.

    child = h;
    h = p;
    p = the next node in the linked list;
    h->less_child = child;

    // Put h onto the stack of less parents.
    h->greater_child = less_parent;
    less_parent = h;

    // Proceed to creating greater than subtree of h.
    branch[depth] = true;
    num_sub = num_sub + rem[depth];
    depth = depth + 1;

END LOOP

// h now points to the root of the completed AVL tree.

pour un encodage de ceci en C++, voir la fonction de membre de compilation (actuellement à la ligne 361) en https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/avl_tree.h . C'est en fait plus général, un modèle utilisant n'importe quel itérateur avancé plutôt que spécifiquement une liste liée.