Pythonで二分探索木（BST）に特定の値が存在するかどうかを判定する方法

問題の概要

二分探索木（BST：Binary Search Tree）と、探索対象となる値 val が与えられたとき、その値が木の中に存在するかどうかを判定するプログラムを作成します。

例えば、次のような二分探索木があったとします。

このとき val = 7 とすると、7は木の中に存在するため、出力は True になります。

アルゴリズムの手順

BSTの性質を利用すると、効率的に値を探索できます。手順は以下の通りです。

• 関数 solve() を定義します。引数として root（現在のノード）と val を受け取ります。

• root が null（None）の場合は False を返します。

• root のデータが val と等しい場合は True を返します。

• root のデータが val より大きい場合は、左部分木に対して solve() を再帰的に呼び出します。

• それ以外の場合は、右部分木に対して solve() を再帰的に呼び出します。

ここでポイントになるのは、BSTが持つ「左側の子孫は親より小さく、右側の子孫は親より大きい」という性質です。この性質のおかげで、各ステップごとに探索すべき範囲が半分に絞られていきます。そのため、バランスの取れた木であれば平均 O(log n) の時間で探索が完了します。

実装例

それでは、実際のコードを見てみましょう。

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


class Solution:
    def solve(self, root, val):
        if not root:
            return False
        if root.data == val:
            return True
        if root.data > val:
            return self.solve(root.left, val)
        return self.solve(root.right, val)


ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)

print(ob.solve(root, 7))

入力

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
val = 7

出力

True

計算量の目安

• 時間計算量： バランスの取れた木では平均 O(log n)。ただし、木が片側に偏って連結リストのような形状になっている最悪ケースでは O(n) になります。

• 空間計算量： 再帰呼び出しに伴うスタック領域として、木の高さ h に比例した O(h) が必要です。

このように、BSTの探索は単純な線形探索と比べて大幅に効率化できるのが大きな魅力です。ぜひ自分でもコードを動かして、挙動を確認してみてください。