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)는 값들이 정렬되어保存在速하게 찾을 수 있도록 합니다.
각 노드는 값을 포함하며 최대 두 개의 자식으로 연결됩니다: 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 규칙

모든 노드에 대해: 왼쪽 서브트리 안의 모든 값은 작고, 오른쪽의 모든 값은 크야야 합니다.
이 하나의 규칙 덕분에 값을 찾으려면 왼쪽이나 오른쪽 중 하나만 이동하면 되며, 두方向을 동시에 갈 필요는 없습니다.

        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은 초기에 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.

한국어

중위 순회(in-order traversal)는 정렬된 순서를 제공합니다

**중위 순회(in-order traversal)**는 왼쪽 서브트리, 그 다음 노드, 그리고 오른쪽 서브트리를 방문합니다.
BST 규칙 덕분에 이 방식은 값을 정렬된 순서로 — 무료로 — 방문합니다.
자연스럽게 재귀적입니다: 왼쪽을 순회하고, 값을 취한 뒤, 오른쪽을 순회합니다.

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.

한국어

이제 직접 해보기

세 가지 핵심 연산을 구현하십시오: insert, in_order, 그리고 contains.
Node 클래스(필요할 때 작동하는 insert 포함)가 제공됩니다.
여러 트리에서 테스트하려면 Answer 확인 버튼을 누르세요.

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