2-3 Trees (Search และ Insert) ใน C/C++

ภาพรวม

2-3 Tree เป็น Balanced Search Tree ที่ทุก Internal Node มี:

• 2-Node: 1 Key, 2 Children
• 3-Node: 2 Keys, 3 Children

คุณสมบัติสำคัญ: ใบไม้ทุกระดับอยู่ระดับเดียวกัน (Perfectly Balanced)

โครงสร้าง Node

2-Node:          3-Node:
   [a]              [a | b]
  /   \            /  |  \
 L     R          L   M   R

กฎการจัดเก็บข้อมูล

• 2-Node: Key a, Left Subtree < L < a, Right Subtree > a
• 3-Node: Keys a < b, Left < a, Middle a < M < b, Right > b

Operations

1. Search (เหมือน BST)

bool search(Node* root, int key) {
    if (!root) return false;
    if (root is 2-node) {
        if (key == root->key1) return true;
        return search(key < root->key1 ? root->left : root->right, key);
    } else { // 3-node
        if (key == root->key1 || key == root->key2) return true;
        if (key < root->key1) return search(root->left, key);
        else if (key < root->key2) return search(root->middle, key);
        else return search(root->right, key);
    }
}

2. Insertion

Insert โดยหาตำแหน่ง Leaf แล้วเพิ่ม Key:

1. Search หา Leaf ที่จะ Insert
2. ถ้า Leaf เป็น 2-Node → กลายเป็น 3-Node (เสร็จ)
3. ถ้า Leaf เป็น 3-Node → Split:
   • แบ่ง 3 Keys ให้ Middle Key ขึ้นไป Parent
   • สร้าง 2-Node ใหม่ 2 ตัว (Left Keys, Right Keys)
   • Parent อาจกลายเป็น 4-Node → Split ต่อขึ้นไป (Cascade)
4. ถ้า Root Split → สร้าง Root ใหม่ (Height เพิ่ม 1)

Insertion Cases (Visual)

Case 1: Insert into 2-Node Leaf
  [10]           [10 | 15]
 /   \    →      /   |   \
...  ...        ...  ... ...

Case 2: Insert into 3-Node Leaf (Split)
  [10 | 20]           [15]
 /  |  \      →      /    \
... ... ...        [10]  [20]

Case 3: Split Propagates to Root (Height Increases)
      [20]                    [30]
     /    \        →          /    \
  [10|25] [40]            [10|20] [25|40]

Complexity Analysis

• Height: O(log n) (Perfectly Balanced)
• Search: O(log n)
• Insert: O(log n) (Split Cascade สูงสุด Height ครั้ง)

โค้ดโครงสร้าง C++ (Outline)

struct Node {
    int keys[2];       // keys[0], keys[1] (keys[1] = 0 if 2-node)
    Node* children[3]; // left, middle, right
    bool isLeaf;
    int keyCount;      // 1 or 2

    Node(int k1) : keyCount(1), isLeaf(true) {
        keys[0] = k1; keys[1] = 0;
        children[0] = children[1] = children[2] = nullptr;
    }
};

// Insert Returns: {newRoot, promotedKey, newRightChild} for Split
// Full implementation is lengthy - see references

ความสัมพันธ์กับ B-Trees

• 2-3 Tree คือ B-Tree of Order 3
• 2-3-4 Tree = B-Tree of Order 4
• Red-Black Tree = Isometric ให้ 2-3-4 Tree

ข้อดี/ข้อเสีย

สรุป

2-3 Tree เป็นพื้นฐานของ B-Trees และ Red-Black Trees ในทางปฏิบัติ ใช้ std::map/std::set (RB-Tree) หรือ B+Tree (Database) แทนได้ เพราะ Implementation ซับซ้อนและ Performance เทียบเท่า