二分探索木

高速な検索・挿入・削除が可能な木構造。

二分探索木

各ノードが最大2つの子を持つ木構造。左の子は親より小さく、右の子は親より大きい。

ノード

木構造の各要素。キー、左の子、右の子を持つ。

根

木構造の最上位ノード。

葉

子を持たないノード。

中間順

左の子、親、右の子の順に走査する。

前順

親、左の子、右の子の順に走査する。

後順

左の子、右の子、親の順に走査する。

平衡

木の左右の高さがほぼ等しい状態。

AVL木

自己平衡二分探索木。挿入・削除時に自動的に平衡を保つ。

二分探索木

家系図

二分探索木は「家系図」のようなもの。各ノードは最大2つの子を持ち、左の子は親より小さく、右の子は親より大きい。ある人を探すとき、親の年齢と比較して、左か右かを決定します。これを繰り返すことで、効率的に人を探せます。

なぜ二分探索木が必要か？

二分探索木は、高速な検索・挿入・削除が可能な木構造です。平均的な計算量はO(log n)で、配列のO(n)よりも効率的です。特に、データの検索・挿入・削除が頻繁な場合に適しています。

いつ使うか？

高速な検索が必要な場合
データの挿入・削除が頻繁な場合
データをソート済みの状態で維持したい場合
範囲検索が必要な場合

実践テクニック

再帰を使う

二分探索木の操作は、再帰を使って簡潔に実装できます。挿入、検索、削除、走査など、多くの操作が再帰的に実装できます。

走査方法を理解する

二分探索木の走査方法には、中間順、前順、後順があります。中間順は、左の子、親、右の子の順に走査し、ソートされた結果を得られます。

計算量を理解する

二分探索木の操作の計算量を理解することは、パフォーマンス最適化に重要です。例：挿入は平均O(log n)、検索は平均O(log n)、走査はO(n)です。これらを理解して、適切なデータ構造を選択します。

平衡を保つ

二分探索木が平衡していない場合、最悪の計算量はO(n)になります。平衡二分探索木（AVL木、赤黒木など）を使うことで、常にO(log n)の計算量を保てます。

1
# 二分探索木の基本操作
2
class Node:
3
    def __init__(self, key):
4
        self.key = key
5
        self.left = None
6
        self.right = None
7

8
class BinarySearchTree:
9
    def __init__(self):
10
        self.root = None
11

12
    def insert(self, key):
13
        self.root = self._insert(self.root, key)
14

15
    def _insert(self, node, key):
16
        if node is None:
17
            return Node(key)
18
        if key < node.key:
19
            node.left = self._insert(node.left, key)
20
        else:
21
            node.right = self._insert(node.right, key)
22
        return node
23

24
    def search(self, key):
25
        return self._search(self.root, key)
26

27
    def _search(self, node, key):
28
        if node is None or node.key == key:
29
            return node
30
        if key < node.key:
31
            return self._search(node.left, key)
32
        return self._search(node.right, key)
33

34
    def delete(self, key):
35
        self.root = self._delete(self.root, key)
36

37
    def _delete(self, node, key):
38
        if node is None:
39
            return node
40
        if key < node.key:
41
            node.left = self._delete(node.left, key)
42
        elif key > node.key:
43
            node.right = self._delete(node.right, key)
44
        else:
45
            # ノードが1つ以下の子を持つ場合
46
            if node.left is None:
47
                return node.right
48
            elif node.right is None:
49
                return node.left
50
            # ノードが2つの子を持つ場合
51
            node.key = self._min_value_node(node.right).key
52
            node.right = self._delete(node.right, node.key)
53
        return node
54

55
    def _min_value_node(self, node):
56
        current = node
57
        while current.left is not None:
58
            current = current.left
59
        return current
60

61
    def inorder(self):
62
        result = []
63
        self._inorder(self.root, result)
64
        return result
65

66
    def _inorder(self, node, result):
67
        if node:
68
            self._inorder(node.left, result)
69
            result.append(node.key)
70
            self._inorder(node.right, result)
71

72
# 使用例
73
bst = BinarySearchTree()
74
bst.insert(50)
75
bst.insert(30)
76
bst.insert(70)
77
bst.insert(20)
78
bst.insert(40)
79
bst.insert(60)
80
bst.insert(80)
81

82
# 検索
83
result = bst.search(40)
84
print(result.key if result else "Not found")  # 40
85

86
# 走査（中間順）
87
print(bst.inorder())  # [20, 30, 40, 50, 60, 70, 80]
88

89
# 削除
90
bst.delete(30)
91
print(bst.inorder())  # [20, 40, 50, 60, 70, 80]

基本操作

二分探索木の基本操作を確認する。

1
# 二分探索木の基本操作
2
class Node:
3
    def __init__(self, key):
4
        self.key = key
5
        self.left = None
6
        self.right = None
7

8
class BinarySearchTree:
9
    def __init__(self):
10
        self.root = None
11

12
    def insert(self, key):
13
        self.root = self._insert(self.root, key)
14

15
    def _insert(self, node, key):
16
        if node is None:
17
            return Node(key)
18
        if key < node.key:
19
            node.left = self._insert(node.left, key)
20
        else:
21
            node.right = self._insert(node.right, key)
22
        return node
23

24
    def search(self, key):
25
        return self._search(self.root, key)
26

27
    def _search(self, node, key):
28
        if node is None or node.key == key:
29
            return node
30
        if key < node.key:
31
            return self._search(node.left, key)
32
        return self._search(node.right, key)
33

34
    def delete(self, key):
35
        self.root = self._delete(self.root, key)
36

37
    def _delete(self, node, key):
38
        if node is None:
39
            return node
40
        if key < node.key:
41
            node.left = self._delete(node.left, key)
42
        elif key > node.key:
43
            node.right = self._delete(node.right, key)
44
        else:
45
            # ノードが1つ以下の子を持つ場合
46
            if node.left is None:
47
                return node.right
48
            elif node.right is None:
49
                return node.left
50
            # ノードが2つの子を持つ場合
51
            node.key = self._min_value_node(node.right).key
52
            node.right = self._delete(node.right, node.key)
53
        return node
54

55
    def _min_value_node(self, node):
56
        current = node
57
        while current.left is not None:
58
            current = current.left
59
        return current
60

61
    def inorder(self):
62
        result = []
63
        self._inorder(self.root, result)
64
        return result
65

66
    def _inorder(self, node, result):
67
        if node:
68
            self._inorder(node.left, result)
69
            result.append(node.key)
70
            self._inorder(node.right, result)
71

72
# 使用例
73
bst = BinarySearchTree()
74
bst.insert(50)
75
bst.insert(30)
76
bst.insert(70)
77
bst.insert(20)
78
bst.insert(40)
79
bst.insert(60)
80
bst.insert(80)
81

82
# 検索
83
result = bst.search(40)
84
print(result.key if result else "Not found")  # 40
85

86
# 走査（中間順）
87
print(bst.inorder())  # [20, 30, 40, 50, 60, 70, 80]
88

89
# 削除
90
bst.delete(30)
91
print(bst.inorder())  # [20, 40, 50, 60, 70, 80]

計算量

二分探索木の操作の計算量を確認する。

1
# 二分探索木の計算量
2
class BinarySearchTree:
3
    # ... (上記の実装を参照)
4

5
# 挿入: 平均O(log n)、最悪O(n)
6
bst.insert(50)
7

8
# 検索: 平均O(log n)、最悪O(n)
9
result = bst.search(40)
10

11
# 削除: 平均O(log n)、最悪O(n)
12
bst.delete(30)
13

14
# 走査: O(n)
15
print(bst.inorder())

使用例

二分探索木の実際の使用例を確認する。

1
# 二分探索木の使用例
2
# データの高速検索
3
class BinarySearchTree:
4
    # ... (上記の実装を参照)
5

6
# 使用例
7
bst = BinarySearchTree()
8
bst.insert(50)
9
bst.insert(30)
10
bst.insert(70)
11

12
# データの検索
13
result = bst.search(30)
14
print(result.key if result else "Not found")  # 30
15

16
# データの削除
17
bst.delete(30)
18
result = bst.search(30)
19
print(result.key if result else "Not found")  # Not found

平衡二分探索木

平衡二分探索木（AVL木）の実装を確認する。

1
# 平衡二分探索木
2
class AVLNode:
3
    def __init__(self, key):
4
        self.key = key
5
        self.left = None
6
        self.right = None
7
        self.height = 1
8

9
class AVLTree:
10
    def __init__(self):
11
        self.root = None
12

13
    def insert(self, key):
14
        self.root = self._insert(self.root, key)
15

16
    def _insert(self, node, key):
17
        # 標準的な挿入
18
        if not node:
19
            return AVLNode(key)
20
        if key < node.key:
21
            node.left = self._insert(node.left, key)
22
        else:
23
            node.right = self._insert(node.right, key)
24

25
        # 高さを更新
26
        node.height = 1 + max(self._get_height(node.left),
27
                             self._get_height(node.right))
28

29
        # 平衡を確認
30
        balance = self._get_balance(node)
31

32
        # 不平衡な場合、回転を行う
33
        if balance > 1 and key < node.left.key:
34
            return self._right_rotate(node)
35
        if balance < -1 and key > node.right.key:
36
            return self._left_rotate(node)
37
        if balance > 1 and key > node.left.key:
38
            node.left = self._left_rotate(node.left)
39
            return self._right_rotate(node)
40
        if balance < -1 and key < node.right.key:
41
            node.right = self._right_rotate(node.right)
42
            return self._left_rotate(node)
43

44
        return node
45

46
    def _get_height(self, node):
47
        if not node:
48
            return 0
49
        return node.height
50

51
    def _get_balance(self, node):
52
        if not node:
53
            return 0
54
        return self._get_height(node.left) - self._get_height(node.right)
55

56
    def _left_rotate(self, z):
57
        y = z.right
58
        T2 = y.left
59

60
        # 回転を行う
61
        y.left = z
62
        z.right = T2
63

64
        # 高さを更新
65
        z.height = 1 + max(self._get_height(z.left),
66
                          self._get_height(z.right))
67
        y.height = 1 + max(self._get_height(y.left),
68
                          self._get_height(y.right))
69

70
        return y
71

72
    def _right_rotate(self, z):
73
        y = z.left
74
        T3 = y.right
75

76
        # 回転を行う
77
        y.right = z
78
        z.left = T3
79

80
        # 高さを更新
81
        z.height = 1 + max(self._get_height(z.left),
82
                          self._get_height(z.right))
83
        y.height = 1 + max(self._get_height(y.left),
84
                          self._get_height(y.right))
85

86
        return y
87

88
    def inorder(self):
89
        result = []
90
        self._inorder(self.root, result)
91
        return result
92

93
    def _inorder(self, node, result):
94
        if node:
95
            self._inorder(node.left, result)
96
            result.append(node.key)
97
            self._inorder(node.right, result)
98

99
# 使用例
100
avl = AVLTree()
101
avl.insert(10)
102
avl.insert(20)
103
avl.insert(30)
104
avl.insert(40)
105
avl.insert(50)
106
avl.insert(25)
107

108
# 走査（中間順）
109
print(avl.inorder())  # [10, 20, 25, 30, 40, 50]

合格ライン

☐ 二分探索木の基本操作ができる

☐ 二分探索木の計算量を理解している

☐ 二分探索木の走査方法を理解している

☐ 平衡二分探索木を理解している

☐ 二分探索木の使い分けができる

演習課題

課題1: 二分探索木の実装

二分探索木クラスを実装し、要素の追加・削除・検索を行うメソッドを作成してください。

課題2: 走査の実装

二分探索木の走査（中間順、前順、後順）を実装してください。

課題3: 平衡二分探索木の実装

平衡二分探索木（AVL木）を実装してください。

参考文献

この記事は以下の公的ガイドライン/標準に基づいています。

Python Data Structures - 公式ドキュメント
Binary Search Tree - Wikipedia
AVL Tree - Wikipedia