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.

ไทย

Binary Search Trees

Binary search tree (BST) เก็บค่าเพื่อให้มันคงความเป็น sorted และค้นหาได้เร็ว
แต่ละ node เก็บค่าและเชื่อมต่อกับ children สูงสุด สอง ตัว:一个 left和一个 right。
Node ด้านบนคือ root. Nodeที่ไม่มี children คือ leaf

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

สำหรับ every node: ทุกอย่างใน left subtree ต้อง เล็กกว่า,ทุกอย่างใน right ต้อง ใหญ่กว่า
กฎเดียวนี้ทำให้คุณสามารถหาค่าด้วยการไปทางซ้ายหรือขวา — ไม่ทั้งสองทาง

        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.

ไทย

Node

เราจำลอง node เป็น object เล็กที่มี value, left, และ right
Node ใหม่ยังไม่มี children ดังนั้น 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.

ไทย

การใส่ค่า

เริ่มที่ root. หาก tree ว่าง ค่าใหม่จะ กลายเป็น root
หากค่าน้อยกว่า node ปัจจุบัน ให้ไป ซ้าย; มิฉะนั้นไป ขวา
ทำซ้ำจนกว่าจะเจอช่องว่าง แล้ววาง node ใหม่ที่นั่น

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 ให้ลำดับ sorted

In-order traversalเยี่ยม: left subtree, แล้วถึง node, จากนั้นไป right subtree.
เนื่องจากกฎของ BST การ遍历นี้จะ访问ค่าตามลำดับที่ sorted — โดยอัตโนมัติ
เป็นแบบ recursive secaraธรรมชาติ:遍历ซ้าย,获取值,遍历ขวา

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

ไทย

การค้นหาเป็นไปอย่างรวดเร็ว

เพื่อหาค่า ให้เปรียบเทียบ它与 node, แล้วไป left หรือ right — ทิ้งhalf ของ tree 在每个步骤中
ใน balanced tree สิ่งนี้ใช้เวลาประมาณ O(log n) ขั้นตอน, เร็วกว่ามากเมื่อเทียบกับการ scan list
Tree ที่มีรูปร่างไม่ดี (ค่าที่ insert ตามลำดับ) สามารถลดลงเป็นเส้นตรง — O(n)

English

Common mistakes

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

ไทย

ข้อผิดพลาดที่พบบ่อย

ใน binary search tree: left child < node < right child
Unbalanced tree จะสูญเสียความได้เปรียบด้านความเร็ว

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.

ไทย

ลองดูเลย

สร้างสาม core operations หลัก: insert, in_order, และ contains
คลาส Node (และตัวแปร working insert ที่จำเป็น) ถูกเตรียมไว้ให้แล้ว
กด Check answer เพื่отестมันบนหลาย trees

Explore · ⁨สำรวจ⁩

Searching a BST · ⁨การค้นหาใน 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. · ⁨คลาส Node ถูกกำหนดไว้. เขียน insert(root, value) ที่เพิ่ม value เข้า BST และ return root. ถ้า root เป็น None, return一个新 Node(value). ถ้า value < root.value ไปทางซ้าย, อื่นๆ ไปทางขวา — และ assign child นั้นกลับไปที่ผลจากการ insert ลงในมัน⁩

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. · ⁨คลิก Run เพื่อดูผลลัพธ์ที่นี่⁩

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 และ insert ที่ทำงานได้ถูกกำหนดไว้. เขียน in_order(root) ที่ return list ของค่าจากการ in-order traversal: subtree ซ้าย, แล้วค่าของโหนดนี้, แล้ว subtree ขวา. ด้วยกฎของ BST รายการที่ได้จะ sorted. ต้นไม้ว่าง (None) ให้ค่า []⁩

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. · ⁨คลิก Run เพื่อดูผลลัพธ์ที่นี่⁩

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 และ insert ที่ทำงานได้ถูกกำหนดไว้. เขียน contains(root, value) ที่ return True ถ้า value อยู่ในต้นไม้, อื่นๆ return False. ใช้กฎ BST: ถ้าเท่ากับโหนดนี้ return True; ถ้าค่าน้อยกว่าค้นหา left, อื่นๆ ค้นหา right; branch ว่าง (None) หมายความว่าไม่มีอยู่⁩

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. · ⁨คลิก Run เพื่อดูผลลัพธ์ที่นี่⁩

Binary search trees