インプレース二分探索木にバイナリツリーを変換する方法、すなわち、我々はすべての余分なスペースを使用することはできません
https://stackoverflow.com/questions/2577098
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
解決
あなたは上に行くために多くを与えることはありませんが、要件は、私はそれが何を考えているならば、あなたはとにかく、あなたはそれをソートしたい方法（既に作成されたバイナリツリーを持っており、メモリに座ったが、ソートされていません）。
私はツリーノードがどのように見えることを仮定しています。
struct tree_node {
struct tree_node * left;
struct tree_node * right;
data_t data;
};
私はまた、あなたが読むことができることを仮定しているC
私たちは、この木は今まで私はそれを無視して、それを並べ替えを扱うますので、私たちに何か良いをしないソート順で作成されずに作成された理由を不思議の周りに座ることもできますが。
最初と最も簡単な解決策は、ソートされていない木がその木から各ノードを削除し、新しいツリーにソートされた挿入を行うための先行順走査を行うことです。これは、Oである（N + N ログ（n））がOであり、（N のログ（N））
これは、彼らが望むものではありません、あなたはしているが、回転やものを使用しているつもりであれば.....
恐ろしい！です私はあなたがヒープソートの奇妙なバージョンを実行して、これを行うことができると思ったが、私は問題に走りました。 恐ろしく遅くなるの心に来たもう一つは、木の上のバブルソートの奇妙なバージョンを行うことを希望ます。
このため、各ノードを比較し、おそらくそれのそれぞれが（またその親を持つため、と）直接の子供と交換され、繰り返しますが、ツリーをトラバースし、任意のを見つけることができませんまで 必要に応じてスワップ。シェーカーソート（右と左へ、左から右に行くバブルソートを）やって、このバージョンは、最高の仕事だろう、と最初のパスの後、あなたはそれの親に対するオーダーの外を見ていなかったサブツリーを下にトラバースする必要はありませんます。
第二の提案のための実行時間の計算を考え出すがかなり複雑になります。最初のIでのバブルとシェーカーソートするように、それは単純にはO（n ^ 2）であろうと思ったが、私はそれが少し良くOより作るのに十分に勝つ（nは^ない場合がありますサブツリートラバーサル回避することを自分自身を満たすことができません2）。基本的にバブルとシェーカーソートはなく、唯一の総sortednessが早期に発生する端部で、あまりにもこの最適化を取得し、あなたは限界を切り倒すことができます。このツリーのバージョンを使用すると、おそらくセットの途中で、同様のチャンクを避けるためにoppurtunitiesを取得します。まあ、私が言ったように、それはおそらく致命的な欠陥がいます。
他のヒント
O（N）で行われ、インプレースすることができ、二重にリンクされたリスト - にバイナリツリーを変換します
そして、ソートそれはnlogn
、マージソートを使用して
変換ツリーにリストバック - O（N）
シンプルnlognソリューションます。
バイナリ検索ツリーを作成後順トラバーサルからの操作を行います。
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';
}
}
ドゥ解に到達するためのアルゴリズムを以下ます。
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）ドゥます。
）INORDERトラバーサルの最初のノードを検索します。それは持っている場合は、ツリーのほとんどの子供を残し、またはそれを持っている場合、最初の右の子、または右の子自体の左にすべきです。 最初のノードの後継inoder見つけるためのアルゴリズム上記b）の使用。 すべての返された後継者のためのc）の手順2を繰り返します。
を使用する2アルゴリズム上記と余分なスペースを使用せずに、バイナリツリーの順トラバーサルで行います。
トラバーサルを行うときに、バイナリ検索ツリーを形成します。しかし、複雑さはO(N2)最悪のケースである。
まあ、私は（ゼロ実際に考えて）口走るしたい最初のものはこれです：再帰的に反復処理全体のバイナリとし、最小の要素を見つけます。バイナリツリーのそれを取り出します。さて、あなたはツリー全体を反復し、最小の要素を見つけるプロセスを繰り返し、最後の要素の親が見られるように（新しいノードの左の子になる前の要素で）それを追加します。オリジナルの木が空になるまで必要な回数として繰り返します。リンクリスト - 終了時に、あなたは最悪のソートされたバイナリツリーが残されています。あなたのポインタが最大の要素であるルートノード、を指している。
最悪の可能なバイナリツリーの出力との時間を実行しているO（N ^ 2）が、それはより良い何かを考え出す前に、まともな出発点だとあなたが書くことができるという利点を持っている -これは、すべての周り恐ろしいアルゴリズムですホワイトボード上の約20行でそのためのコードます。
二分木がのない変換が必要とされない場合、二分探索木、。
おそらくあなたは、あなたから変換しているものの構造を明確にする必要があります。あなたのソースツリーはアンバランスですか？それはあなたが検索したいキーによって順序付けされていませんか？どのようにソースツリーに到着したのですか？
#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;
}
struct Node
{
int value;
Node* left;
Node* right;
};
void swap(int& l, int& r)
{
int t = l;
l = r;
r = t;
}
void ConvertToBST(Node* n, Node** max)
{
if (!n) return;
// leaf node
if (!n->left && !n->right)
{
*max = n;
return;
}
Node *lmax = NULL, *rmax = NULL;
ConvertToBST(n->left, &lmax);
ConvertToBST(n->right, &rmax);
bool swapped = false;
if (lmax && n->value < lmax->value)
{
swap(n->value, lmax->value);
swapped = true;
}
if (rmax && n->value > rmax->value)
{
swap(n->value, n->right->value);
swapped = true;
}
*max = n;
if (rmax && rmax->value > n->value) *max = rmax;
// If either the left subtree or the right subtree has changed, convert the tree to BST again
if (swapped) ConvertToBST(n, max);
}
ドゥバイナリツリーのトラバーサルINORDERと結果を格納します。 順番をacendingに結果を並べ替えます （これはバイナリ検索を使用して行うことができます）ルートとして分類されたリストの真ん中の要素を取ることによって、バイナリ検索ツリーを形成します。私たちは、二分探索木をバランスます。
ヒープソートツリー.. nlogn複雑..
