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.

Tiếng Việt

Cây tìm kiếm nhị phân

Một cây tìm kiếm nhị phân (BST) lưu trữ các giá trị sao cho chúng được sắp xếp và tìm kiếm nhanh.
Mỗi nút chứa một giá trị và liên kết với tối đa hai con: một left và một right.
Nút trên cùng là gốc. Một nút không có nút con là lá.

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.

Tiếng Việt

Quy tắc BST

Đối với mọi nút: tất cả những gì trong cây con trái của nó đều nhỏ hơn, tất cả những gì trong cây con phải đều lớn hơn.
Một quy tắc duy nhất này cho phép bạn tìm thấy giá trị bằng cách đi sang trái hoặc phải — chưa bao giờ cả hai.

        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.

Tiếng Việt

Một nút

Chúng ta mô hình hóa một nút như một đối tượng nhỏ có value, left, và right.
Một nút mới hoàn toàn chưa có con nào, nên left và right bắt đầu là 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.

Tiếng Việt

Chèn một giá trị

Bắt đầu từ gốc. Nếu cây trống, giá trị mới sẽ trở thành gốc.
Nếu giá trị nhỏ hơn nút hiện tại, hãy đi trái; ngược lại hãy đi phải.
Lặp lại cho đến khi chạm đến vị trí trống, và đặt nút mới vào đó.

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.

Tiếng Việt

Duyệt theo thứ tự trung tâm mang lại thứ tự sắp xếp

Duyệt theo thứ tự (in-order traversal) truy cập: cây con trái, sau đó là nút, rồi đến cây con phải.
Do quy tắc BST, việc này truy cập các giá trị theo thứ tự đã sắp xếp — miễn phí.
Nó mang tính đệ quy tự nhiên: duyệt trái, lấy giá trị, duyệt phải.

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).

Tiếng Việt

Tìm kiếm diễn ra nhanh chóng

Để tìm một giá trị, hãy so sánh nó với nút hiện tại, sau đó di chuyển sang trái hoặc phải — loại bỏ một nửa cây ở mỗi bước.
Trong một cây cân bằng, điều này mất khoảng O(log n) bước, nhanh hơn nhiều so với quét qua danh sách.
Một cây có hình dạng kém (giá trị được chèn đã được sắp xếp) có thể suy giảm thành một đường thẳng — O(n).

English

Common mistakes

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

Tiếng Việt

Lỗi thường gặp

Trong cây tìm kiếm nhị phân: con trái < nút < con phải.
Một cây không cân bằng sẽ mất đi lợi thế về tốc độ.

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.

Tiếng Việt

Bây giờ bạn thử

Xây dựng ba thao tác cốt lõi: insert, in_order, và contains.
Lớp Node (và một lớp insert hoạt động, nơi bạn cần nó) đã được cung cấp.
Nhấn Kiểm tra câu trả lời để thử nghiệm trên nhiều cây khác nhau.

Explore · ⁨Khám phá⁩

Searching a BST · ⁨Tìm kiếm trong BST⁩

Left is smaller, right is bigger — so each step skips half the tree. · ⁨Trái nhỏ hơn, phải lớn hơn—vì vậy mỗi bước bỏ qua một nửa cây.⁩

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 đã được cung cấp. Viết insert(root, value) thêm value vào BST và trả về root. Nếu root là None, trả về một ⟨Node(value)⟩ mới. Nếu value < root.value đi sang trái, ngược lại đi sang phải—và gán lại con trỏ đó với kết quả của việc chèn vào nó.⁩

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. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

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 []. · ⁨Node và một ⟨insert⟩ hoạt động tốt đã được cung cấp. Viết ⟨in_order(root)⟩ trả về một danh sách các giá trị từ duyệt inorder: cây con trái, sau đó giá trị của node hiện tại, rồi cây con phải. Nhờ quy tắc BST, danh sách sẽ được sắp xếp theo thứ tự tăng dần. Cây rỗng (None) cho ra ⟨[]⟩.⁩

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. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

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. · ⁨Node và một ⟨insert⟩ hoạt động tốt đã được cung cấp. Viết ⟨contains(root, value)⟩ trả về ⟨True⟩ nếu ⟨value⟩ có trong cây, ngược lại trả về ⟨False⟩. Sử dụng quy tắc BST: nếu bằng node hiện tại thì trả về ⟨True⟩; nếu nhỏ hơn thì tìm kiếm trái, ngược lại tìm kiếm phải; nhánh rỗng (None) nghĩa là không có mặt.⁩

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. · ⁨Nhấn Chạy để xem kết quả ở đây.⁩

Binary search trees · ⁨Cây nhị phân tìm kiếm (BST)⁩