ツリーと再帰【Algorithm-Data構造入門Ⅳ】

ツリーの概念

ツリーは、データ構造の一種であり、木構造とも呼ばれます。ツリーは根（root）と呼ばれるノードから始まり、枝分かれするようにして複数のノードが連なっています。それぞれのノードは、子ノードを持つことができますが、親ノードは一つだけです。ツリーは階層構造を持ち、データを効率的に管理するのに役立ちます。

完全２分木の性質

完全２分木は、すべての葉が同じ深さを持ち、かつ全てのノードが0個または2個の子ノードを持つ二分木です。このような性質を持つ完全２分木では、ノード数がN個の場合、高さはlog(N)になります。これは、ツリー内の各レベルでノード数が２倍になるためです。

完全２分木の表現

以下の例では、要素数が6の完全２分木を考えます。

         [0]
       /     \
     [1]     [2]
    /   \   /   \
  [3]  [4] [5]  [6]

この完全２分木は、インデックスを使って配列で表現されます。この場合、各ノードのインデックスは次のようになります。

・根：0
・左の子：親のインデックス * 2 + 1
・右の子：親のインデックス * 2 + 2

例えば、インデックス４は上の式に当てはめると、親から見て右の子のため、
親のインデックス[1] × 2 + 2 = 4となります。

この方法を使うと、配列を使ってツリーを表現することができます。
以下は、配列を用いて完全２分木を表現するためのPythonのクラスとその使用例です。
是非図と見比べながら確認してみてください。

class CompleteBinaryTree:
	def __init__(self, size):
		self.tree = [None] * size  # 要素がNoneで初期化された配列を作成

	# 	要素を挿入
	def insert(self, index, value):
		self.tree[index] = value

	# 	完全二分木を取得
	def get_tree(self):
		return self.tree

	# 	親ノードのインデックスを取得
	def	 get_parent_index(self, i):
		return (i - 1) // 2

	# 	左の子ノードのインデックスを取得
	def	 get_left_child_index(self, i):
		return 2 * i + 1

	# 	右の子ノードのインデックスを取得
	def	 get_right_child_index(self, i):
		return 2 * i + 2

	# 	根のノードを取得
	def	 get_root(self):
		return self.tree[0]

	# 	左の子ノードを取得
	def	 get_left_child(self, i):
		left_index = self.get_left_child_index(i)
		if left_index < len(self.tree):
			return self.tree[left_index]
		else:
			return None

	# 	右の子ノードを取得
	def	 get_right_child(self, i):
		right_index = self.get_right_child_index(i)
		if right_index < len(self.tree):
			return self.tree[right_index]
		else:
			return None

# 完全二分木の使用例
tree = CompleteBinaryTree(6)
tree.insert(0, "A")
tree.insert(1, "B")
tree.insert(2, "C")
tree.insert(3, "D")
tree.insert(4, "E")
tree.insert(5, "F")
print(tree.get_tree()) # Output: ['A', 'B', 'C', 'D', 'E', 'F']
print(tree.get_root()) # Output: A
print(tree.get_left_child(1)) # Output: D
print(tree.get_right_child(1)) # Output: E
print(tree.get_left_child(2)) # Output: F
print(tree.get_right_child(2)) # Output: None
print(tree.get_parent_index(5)) # Output: 2

上記の例では、ツリーは以下のような構造になっています。

         'A'
       /     \
     'B'     'C'
    /   \   /   \
  'D'  'E' 'F'  None

再起の概念

再帰は、自分自身を呼び出す関数や手続きのことを指します。再帰を使うことで、問題をより小さな部分問題に分割し、解決することができます。再帰は、特にツリー構造や階層的なデータ構造を扱う際に有用です。

Pythonでは、再帰を使用して簡潔なコードを書くことができます。
フィボナッチ数列を考えてみましょう。

フィボナッチ数列は、再帰の代表的な例です。フィボナッチ数列は以下のように定義されます。

・F(0) = 0
・F(1) = 1
・F(n) = F(n-1) + F(n-2) （n ≥ 2）

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

再帰木を用いた再帰algorithmの時間計算量

再帰を用いたアルゴリズムの時間計算量を求める際には、再帰木を使って考えることが一般的です。再帰木は、再帰呼び出しがどのように展開されるかを表す木構造です。ノードは再帰呼び出しを表し、枝は各呼び出しで実行される処理を表します。

先ほどのフィボナッチ数列の計算を例に考えてみましょう。

再掲

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

この関数では、fibonacci(n) を計算する際に fibonacci(n-1) と fibonacci(n-2) を再帰的に呼び出しています。

再帰木を用いて、この関数の時間計算量を求めるには、各再帰呼び出しでの計算量を考慮し、再帰木の高さを調べます。

以下は、fibonacci(5) を計算する際の再帰木の構造を示したものです。

                  fib(5)
              /           \
         fib(4)         fib(3)
       /       \       /       \
   fib(3)   fib(2)   fib(2)   fib(1)
  /     \    /    \   /    \
fib(2) fib(1) fib(1) fib(0) fib(1)
  /   \
fib(1) fib(0)

この再帰木では、同じ引数に対する再帰呼び出しが複数回行われています。これにより、同じ部分問題が繰り返し計算されます。

このような再帰木の高さを考えると、再帰関数の呼び出し回数は指数的に増加します。したがって、この再帰アルゴリズムの時間計算量は指数時間となります。

具体的には、fibonacci(n) を計算する際に、同じ引数に対する再帰呼び出しが2回行われるため、指数的に増加します。そのため、このアルゴリズムの時間計算量はO(2^n)となります。

このように、再帰木を用いて再帰アルゴリズムの時間計算量を求めることができます。ただし、指数時間のアルゴリズムは大きな入力に対しては非常に効率が悪いため、フィボナッチ数列のような問題に対しては他の効率的なアルゴリズムを探すことが重要です。

まとめ

ツリーと再帰は、コンピュータサイエンスにおいて非常に重要な概念です。ツリーはデータの階層的な構造を表現するために使われ、再帰は問題をより小さな部分問題に分割するための強力なツールです。再帰を理解し、ツリーを操作する方法をマスターすることは、プログラミングにおいて重要なスキルでしょう！