Binary search trees

English

A binary search tree (BST) stores values so they stay sorted and are fast to find.
Each node holds a value and links to up to two children: a left and a right.
The top node is the root. A node with no children is a leaf.

日本語

二分探索木

二分探索木（BST） は値を格納し、整列された状態で保持しつつ、高速に検索できるようにします。
各ノードは値を持ち、最大2つの子供へのリンクを持っています：左のleft と右のright です。
一番上のノードをルートといいます。子供を持たないノードをリーフといいます。

English

The BST rule

For every node: everything in its left subtree is smaller, everything in its right is larger.
This one rule is what lets you find a value by going left or right — never both.

日本語

BSTのルール

すべてのノードについて：その左部分木にあるものはすべて小さく、右部分木にあるものはすべて大きいです。
この1つのルールこそが、左右どちらかに進むことで値を見つけることを可能にし、両方進む必要がないようにします。

        5
       / \
      3   8
     / \   \
    1   4   9

left < node < right, at every node

English

A node

We model a node as a small object with a value, a left, and a right.
A brand-new node has no children yet, so left and right start as None.

日本語

ノード

ノードを、value、left、right を持つ小さなオブジェクトとしてモデル化します。
新規ノードにはまだ子供がないため、left とright は initially None として始まります。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

n = Node(5)
print(n.value)   # 5
print(n.left)    # None

English

Inserting a value

Start at the root. If the tree is empty, the new value becomes the root.
If the value is smaller than the current node, go left; otherwise go right.
Repeat until you reach an empty spot, and put the new node there.

日本語

値の挿入

ルートから始めます。木が空であれば、新しい値がルートとなります。
値が現在のノードより小さい場合は左へ、そうでなければ右へ進みます。
空の場所が見つかるまで繰り返し、そこに新しいノードを置きます。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

root = None
for v in [5, 3, 8, 1]:
    root = insert(root, v)
print(root.value)            # 5
print(root.left.value)       # 3
print(root.right.value)      # 8

English

In-order traversal gives sorted order

In-order traversal visits: the left subtree, then the node, then the right subtree.
Because of the BST rule, this visits the values in sorted order — for free.
It is naturally recursive: traverse left, take the value, traverse right.

日本語

インオーダー走査は整列順序を与える

インオーダー順回は、左部分木を visiting、次にノードを visiting、最後に右部分木を visiting します。
BSTのルールにより、この順序で値がソートされた状態で取得できるため、追加コストは発生しません。
自然に再帰的です：左を traversal し、値を取得し、右を traversal します。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    if root is None:
        return []
    return in_order(root.left) + [root.value] + in_order(root.right)

root = None
for v in [5, 3, 8, 1, 4]:
    root = insert(root, v)
print(in_order(root))   # [1, 3, 4, 5, 8]

English

Searching is fast

To find a value, compare it with the node, then go left or right — skipping half the tree each step.
In a balanced tree this takes about O(log n) steps, much faster than scanning a list.
A badly-shaped tree (values inserted already sorted) can degrade to a line — O(n).

日本語

検索は高速です

値を探すには、ノードと比較して左または右へ移動し、各ステップでツリーのおよそ半分をスキップします。
バランスが取れたツリーでは、これはおおよそ O(log n) ステップで完了し、リストの走査よりも遥かに速いです。
形が悪く（値が既にソートされた状態で挿入された）ツリーは線分のような構造になり、O(n) に劣化します。

English

Common mistakes

In a binary search tree: left child < node < right child.
An unbalanced tree loses the speed advantage.

日本語

よくあるミス

二項探索木において：左の子 < ノード < 右の子です。
バランスが取れていないツリーでは、速度の利点が失われます。

English

Now you try

Build the three core operations: insert, in_order, and contains.
The Node class (and a working insert, where you need it) is provided.
Press Check answer to test it on several trees.

日本語

あなたも試してみよう

3つの主要な操作を構築します：insert、in_order、および contains。
Node クラス（必要に応じて動作する insert）が提供されています。
回答を確認 を押して、いくつかのツリー上でテストしてください。

Explore · ⁨探索⁩

Searching a BST

Left is smaller, right is bigger — so each step skips half the tree.

The Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root is None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    # Empty -> new Node. Else go left if smaller, right otherwise. Return root.
    pass

Click Run to see the output here. · ⁨実行ボタンをクリックして出力を確認してください。⁩

Node and a working insert are provided. Write in_order(root) that returns a list of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives [].

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    # Return left values + [this value] + right values; [] when root is None
    pass

Click Run to see the output here. · ⁨実行ボタンをクリックして出力を確認してください。⁩

Node and a working insert are provided. Write contains(root, value) that returns True if value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search left, otherwise search right; an empty branch (None) means it is not there.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def contains(root, value):
    # None -> False. Equal -> True. Smaller -> search left, else search right.
    pass

Click Run to see the output here. · ⁨実行ボタンをクリックして出力を確認してください。⁩

Binary search trees