algorithm - 二分木をその場で二分探索木に変換する方法、つまり余分なスペースを使用できない

Question

二分木をその場で二分探索木に変換する方法。つまり、余分なスペースは使用できません。

Answer 1

バイナリ ツリーを二重リンク リストに変換します。O(n) でインプレースで実行できます
。次に、マージ ソートを使用して並べ替えます。nlogn
リストをツリーに変換します - O(n)

シンプルな nlogn ソリューション。

Answer 2

先に進むことはあまりありませんが、要件が私が考えているものである場合、バイナリツリーは既に作成されており、メモリに格納されていますが、ソートされていません(とにかく、ソートしたい方法です)。

ツリーノードは次のように見えると想定しています

struct tree_node {
    struct tree_node * left;
    struct tree_node * right;
    data_t data;
};

また、Cが読めると仮定しています

ソートされた順序で作成されずに、なぜこのツリーが作成されたのか疑問に思うこともできますが、それは何の役にも立たないので、無視してソートするだけにします。

余分なスペースを使用しないという要件は奇妙です。スタック上にのみ、一時的に余分なスペースがあります。malloc などを呼び出すこと、および結果のツリーが元のソートされていないツリーよりも多くのメモリを使用する必要がないことを意味すると仮定します。

最初の最も簡単な解決策は、ソートされていないツリーの事前順序トラバーサルを実行して、そのツリーから各ノードを削除し、新しいツリーにソートされた挿入を行うことです。これは O(n+n log(n)) であり、O(n log(n)) です。

これが彼らの望んでいるものではなく、ローテーションなどを使わなければならない場合.....それは恐ろしいことです!

奇妙なバージョンのヒープソートを実行することでこれを実行できると思っていましたが、問題が発生しました。頭に浮かんだもう 1 つのことは、恐ろしく遅いですが、ツリーで奇妙なバージョンのバブル ソートを実行することです。

このため、各ノードは、ツリーを走査して必要なスワップが見つからなくなるまで、その直接の子 (したがってその親とも) のそれぞれと比較され、場合によってはスワップされます。これのシェーカー ソート (左から右、右から左に進むバブル ソート) バージョンを実行すると、最もうまく機能し、最初のパスの後、親に関して順不同に見えなかったサブツリーをたどる必要はありません。 .

このアルゴリズムは、私の前に他の誰かによって考え出され、私が知らないクールな名前を持っているか、私が見ていない何らかの方法で根本的に欠陥があると確信しています.

2 番目の提案の実行時の計算を考え出すのはかなり複雑です。最初は、バブルやシェーカーの並べ替えのように、単純に O(n^2) になると思っていましたが、サブツリー トラバーサルの回避では、O(n^ 2)。基本的に、バブルとシェーカーの並べ替えもこの最適化を取得しますが、完全な並べ替えが早期に発生し、制限を切り詰めることができる端でのみです。このツリー バージョンでは、セットの途中でチャンクを回避する機会も得られます。おっしゃる通り、おそらく致命的な欠陥です。

Answer 3

PostOrder Traversal を実行し、そこから二分探索木を作成します。

struct Node * newroot = '\0';

struct Node* PostOrder(Struct Node* root)
{
      if(root != '\0')
      {
          PostOrder(root->left);
          PostOrder(root->right);
          insertBST(root, &newroot);
      }
}

insertBST(struct Node* node, struct Node** root)
{
   struct Node * temp, *temp1;
   if( root == '\0')
   {
      *root == node;
       node->left ==  '\0';
       node->right == '\0';
   }
   else
   {
       temp = *root;
       while( temp != '\0')
       {
           temp1= temp;
           if( temp->data > node->data)
               temp = temp->left;
           else
               temp = temp->right;
       }
       if(temp1->data > node->data)
       {
           temp1->left = node;
       }
       else
       {
           temp1->right = node;
       }
       node->left = node->right = '\0';
    }
}

Answer 4

解に到達するには、次のアルゴリズムを実行します。

1) スペースを使用せずに順番に後続を検索します。

Node InOrderSuccessor(Node node)
{ 
    if (node.right() != null) 
    { 
        node = node.right() 
        while (node.left() != null)  
            node = node.left() 
        return node 
    }
    else
    { 
        parent = node.getParent(); 
        while (parent != null && parent.right() == node)
       { 
            node = parent 
            parent = node.getParent() 
        } 
        return parent 
    } 
} 

2) スペースを使用せずに順番にトラバーサルを行います。

a) inorder traversal の最初のノードを見つけます。ツリーのほとんどの子が残っている場合は、最初の右の子の左、または右の子自体が残っている必要があります。b) 上記のアルゴリズムを使用して、最初のノードの inode サクセサを見つけます。c) 返されたすべてのサクセサに対してステップ 2 を繰り返します。

上記の 2 アルゴリズムを使用して、余分なスペースを使用せずに二分木を順番にトラバーサルします。トラバーサルを行うときに二分探索木を形成します。しかし、複雑さはO(N2)最悪のケースです。

Answer 5

バイナリツリーは通常、バイナリ検索ツリーであり、この場合、変換は必要ありません。

おそらく、変換元の構造を明確にする必要があります。ソースツリーのバランスが崩れていませんか？検索したいキー順ではありませんか？どのようにしてソースツリーに到達しましたか？

Answer 6

さて、これがインタビューの質問である場合、私が最初に（実際の考えはゼロで）ぼかすのはこれです：バイナリ全体を再帰的に繰り返し、最小の要素を見つけます。二分木からそれを取り出します。ここで、ツリー全体を繰り返して最小の要素を見つけるプロセスを繰り返し、最後に見つかった要素の親として追加します（前の要素が新しいノードの左の子になります）。元のツリーが空になるまで、必要な回数だけ繰り返します。最後に、可能な限り最悪のソートされたバイナリツリー（リンクリスト）が残ります。ポインタは、最大の要素であるルートノードを指しています。

これは万能の恐ろしいアルゴリズムです-O（n ^ 2）の実行時間で、可能な限り最悪のバイナリツリー出力がありますが、より良いものを思い付く前の適切な開始点であり、次のコードを記述できるという利点があります。ホワイトボードに約20行で表示されます。

Answer 7

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

struct tree_node {
    struct tree_node * left;
    struct tree_node * right;
    data_t data;
};

        /* a bonsai-tree for testing */
struct tree_node nodes[10] =
{{ nodes+1, nodes+2, 1}
,{ nodes+3, nodes+4, 2}
,{ nodes+5, nodes+6, 3}
,{ nodes+7, nodes+8, 4}
,{ nodes+9, NULL, 5}
,{ NULL, NULL, 6}
,{ NULL, NULL, 7}
,{ NULL, NULL, 8}
,{ NULL, NULL, 9}
        };

struct tree_node * harvest(struct tree_node **hnd)
{
struct tree_node *ret;

while (ret = *hnd) {
        if (!ret->left && !ret->right) {
                *hnd = NULL;
                return ret;
                }
        if (!ret->left ) {
                *hnd = ret->right;
                ret->right = NULL;;
                return ret;
                }
        if (!ret->right) {
                *hnd = ret->left;
                ret->left = NULL;;
                return ret;
                }
        hnd = (rand() &1) ? &ret->left : &ret->right;
        }

return NULL;
}

void insert(struct tree_node **hnd, struct tree_node *this)
{
struct tree_node *ret;

while ((ret= *hnd)) {
        hnd = (this->data  < ret->data ) ? &ret->left : &ret->right;
        }
*hnd = this;
}

void show(struct tree_node *ptr, int indent)
{
if (!ptr) { printf("Null\n"); return; }

printf("Node(%d):\n", ptr->data);
printf("%*c=", indent, 'L');  show (ptr->left, indent+2);
printf("%*c=", indent, 'R');  show (ptr->right, indent+2);
}

int main(void)
{
struct tree_node *root, *this, *new=NULL;

for (root = &nodes[0]; this = harvest (&root);  ) {
        insert (&new, this);
        }

show (new, 0);
return 0;
}

Answer 8

二分木を順番にたどり、結果を格納します。ソートされたリストの中間要素をルートとして取得することにより、バイナリ検索ツリーから昇順で結果をソートします（これはバイナリ検索を使用して実行できます）。したがって、バランスの取れた二分探索木が得られます。

Answer 9

ツリーをヒープソート.. nlogn 複雑さ..