0

埋め込む：

bool tree_isBalanced(tree_t tree);
    // EFFECTS: returns true if tree is balanced, false otherwise

あなたのために実装されていると仮定できる次の機能を考えると：

bool tree_isEmpty(tree_t tree);
   // EFFECTS: returns true if tree is empty, false otherwise

tree_t tree_make();
   // EFFECTS: creates an empty tree.

tree_t tree_make(int elt, tree_t left, tree_t right);
   // EFFECTS: creates a new tree, with elt as it's element, left as
   //          its left subtree, and right as its right subtree

int tree_elt(tree_t tree);
   // REQUIRES: tree is not empty
   // EFFECTS: returns the element at the top of tree.

tree_t tree_left(tree_t tree);
   // REQUIRES: tree is not empty
   // EFFECTS: returns the left subtree of tree

tree_t tree_right(tree_t tree);
   // REQUIRES: tree is not empty
   // EFFECTS: returns the right subtree of tree

ツリーのすべてのノードで右側のサブツリーと左側のサブツリーが同じ高さである場合、ツリーはバランスが取れています。ツリーの高さは、ツリーのルートからツリーの最も深いノードまでのパスに存在するノードの数として定義されます。ノードが 1 つしかないツリーの高さは 1 で、空のツリーの高さは 0 です。したがって、空のツリーは自明に完全にバランスが取れていると見なされます。

ツリーを下に移動するときに成長する再帰にどのように対処できますか?

4

1 に答える 1

0

それはあなたが心配している再帰成長のどの側面に依存します。再帰呼び出しの総数が心配な場合は、ここでの一般的な実装はO（N）の合計呼び出しであり、Nはツリーノードの数であることに注意してください。高さの定義はノードごとであるため、O（N）よりも優れているとは想像しがたいです。

最大再帰深度が心配で、コールスタックが吹き飛ばされる可能性がある場合、できることの1つは、コールスタックをまったく使用しないことです。つまり、代わりに、標準のスタックオブジェクトの上で動作するループとして再帰を実装します。内部的には、これによりメモリ使用量の大部分がヒープに移動され（基になるリスト、両端キューなどの動的な再割り当てによって）、コールスタックのフラッディングが防止されます。（メモリ使用量とスタックとヒープの説明は、実際にはC ++の実装に依存することに注意してください。ただし、私の知る限り、すべての主要なPC環境に適用されます）。

于 2012-10-19T18:08:14.177 に答える