8

値のリストを指定して完全な二分探索木を作成するアルゴリズムを作成しようとしています。すべての要素を可能な限り左にシフトする必要がある最後のレベルを除いて、すべてのレベルがいっぱいであるという点で完了です。

次のように、バランスの取れた BST を作成するものを (Python で) 実装しました。

# TreeNode constructor takes (data, left, right, parent)
def make_tree(arr, parent):
    if not arr:
        return None

    length = len(arr)
    if length == 1:
        return TreeNode(arr[0], None, None, parent)
    else:
        mid = int(len(arr)/2)
        mid_node = TreeNode(arr[mid], None, None, parent)
        mid_node.left = make_tree(arr[0:mid], mid_node)
        mid_node.right = make_tree(arr[mid+1:length], mid_node)
        return mid_node

リストを中間点で再帰的に分割し、中間点を親ノードにすることで機能します。

ただし、これは完全なBSTを作成しません。リスト [2,4,7,8,10] を指定すると、次のように作成されます。

      7

   /    \ 

  4     10

/       /

2      8

しかし、完全な BST は次のようになります。

      8

   /    \ 

  4     10

 /  \ 

2    7

これを達成するために私のアプローチを変更する方法について何か提案はありますか?

4

2 に答える 2

5

完全な BST の構成は、バランスのとれた BST の構成に似ています。正しい中央を見つけるだけです。次の関数を使用しました。

def perfect_tree_partition(n):
    """find the point to partition n keys for a perfect binary tree"""
    x = 1

    # find a power of 2 <= n//2
    # while x <= n//2:  # this loop could probably be written more elegantly :)
    #     x *= 2
    x = 1 << (n.bit_length() - 1)   # indeed you can

    if x//2 - 1 <= (n-x):
        return x - 1      # case 1
    else:
        return n - x//2   # case 2 == n - (x//2 - 1) - 1

次の 2 つの場合があります。

  • ケース 1:ルートの左側のサブツリーが完全で、右側のサブツリーのノードが少ない、または
  • ケース 2:ルートの左側のサブツリーにはより多くのノードがあり、右側のサブツリーは完全です。

どちらの場合も、完全なサブツリー内のノードの数はいくらかである2**d - 1ため、ルートは2**d左 (ケース 1) または右 (ケース 2) から数えて th 番目のノードです。1インデックスは から始まるため、減算するだけ0です。

于 2014-11-12T21:01:55.283 に答える
-1

これが 1 回限りの操作である場合は、最初にリストを並べ替えてから BST を作成できます。それは問題を簡単にします。

于 2013-10-10T19:32:45.843 に答える