arbre binaire à binaire arbre de recherche (BST)

Question

Comment convertir Binary Tree Binary arbre de recherche avec O (1) espace supplémentaire?

Answer 1

Conversion d'un arbre binaire dans un arbre non ordonnée de recherche binaire commandé est trivial, mais un peu plus difficile à faire vite.

Voici une implémentation naïve qui devrait satisfaire vos critères, je ne vais pas décrire les étapes réelles à prendre, juste l'algorithme général.

1. Faire un nœud aléatoire des feuilles de votre arbre existant
2. Dissociez le nœud feuille de votre arbre existant
3. Faire le nœud la racine de votre nouvel arbre de recherche binaire
4. Faire un autre nœud de feuille au hasard de votre arbre existant
5. Dissocier ce nœud de votre arbre existant
6. Trouver le bon endroit pour et relier le nœud, dans votre nouvel arbre de recherche binaire
7. Répétez l'étape 4-6 jusqu'à ce que l'arborescence d'origine soit vide

Vous ne devez utiliser que quelques variables, comme le parent du noeud feuille que vous dissociez (sauf si les nœuds ont des liens parents), le noeud racine du nouvel arbre, et quelques variables temporaires, toutes dans votre critère d'espace O (1).

Cela ne produira pas un arbre binaire de recherche optimale. Pour cela, vous devez soit trier les nœuds avant de les ajouter, et les ajouter dans le bon ordre, ou utiliser un arbre de recherche binaire d'équilibrage, comme un arbre rouge-noir ou un arbre splay.

Answer 2

Convertir Binary Tree à un liste- doublement lié peut être fait inplace en O (n) ensuite trier en utilisant le tri par fusion, nlogn Convertir la liste Retour à un arbre - O (n)

Simple nlogn Solution.