26.4 binary search tree

หน้า 20.1 บอกว่าข้างใน set เป็นต้นไม้ค้นหา ซึ่งหาค่า ใส่ และลบได้ใน O(log N) หน้านี้เขียนต้นไม้แบบนั้นเองตั้งแต่ต้น ใส่ ค้นหา พิมพ์ค่าเรียงจากน้อยไปมาก และลบ แล้ววัดให้เห็นว่าต้นไม้ที่เขียนเองมีจุดอ่อนใหญ่ที่ set ไม่มี คือถ้าใส่ข้อมูลที่เรียงมาแล้ว ต้นไม้จะเอียงเป็นเส้นตรง และทุกคำสั่งช้าลงเป็น O(N) เข้าใจข้อนี้แล้วจะรู้ว่าเมื่อไรเขียนเองได้ และเมื่อไรต้องใช้ set

กฎของต้นไม้ค้นหา

binary search tree (BST ต้นไม้ค้นหาแบบทวิภาค) คือ binary tree ที่ทุกโหนดเก็บค่าหนึ่งค่า เรียกว่า คีย์ (key) และทุกโหนดทำตามกฎข้อเดียว

กฎของ BST

ทุกคีย์ในต้นไม้ย่อยซ้ายของโหนด v น้อยกว่าคีย์ของ v และทุกคีย์ในต้นไม้ย่อยขวามากกว่าคีย์ของ v

หน้านี้ถือว่าคีย์ไม่ซ้ำกัน เหมือน set ภาพนี้คือต้นไม้ของส่วนสูงนักเรียนเจ็ดคนจากหน้า 20.1 ทางที่เป็นเส้นหนาคือทางค้นหา 171

กฎนี้ใช้กับทั้งต้นไม้ย่อย ไม่ใช่แค่ลูกโดยตรง 158 อยู่ใต้ 152 ทางขวา จึงต้องมากกว่า 152 และเพราะอยู่ในต้นไม้ย่อยซ้ายของ 165 จึงต้องน้อยกว่า 165 ด้วย ผลที่ได้คือ การค้นหาเริ่มจากราก เทียบกับคีย์ของโหนดปัจจุบัน น้อยกว่าไปซ้าย มากกว่าไปขวา แต่ละก้าวทิ้งต้นไม้ย่อยอีกข้างไปทั้งหมด เหมือน binary search ในบทที่ 19 ที่ทิ้งครึ่งหนึ่งของช่วง

ใส่และค้นหา

การใส่คีย์ใหม่คือการค้นหาคีย์นั้นจนตกลงไปที่ที่ว่าง แล้วแขวน node ใหม่ไว้ตรงนั้น node ใหม่จึงเป็นใบเสมอ ทั้งสองงานเขียนด้วยลูปเดินลงทีละชั้นได้ ไม่ต้องใช้ recursion

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *left;
    Node *right;
};

Node *insert(Node *root, int key)
{
    Node *node = new Node;
    node->key = key;
    node->left = nullptr;
    node->right = nullptr;
    if (root == nullptr) { // (1)!
        return node;
    }
    Node *cur = root;
    while (true) {
        if (key < cur->key) { // (2)!
            if (cur->left == nullptr) {
                cur->left = node;
                break;
            }
            cur = cur->left;
        } else {
            if (cur->right == nullptr) {
                cur->right = node;
                break;
            }
            cur = cur->right;
        }
    }
    return root;
}

void find_key(Node *root, int key)
{
    cout << "search " << key << ':';
    Node *cur = root;
    while (cur != nullptr && cur->key != key) { // (3)!
        cout << ' ' << cur->key;
        if (key < cur->key) {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
    }
    if (cur == nullptr) {
        cout << " not found\n";
    } else {
        cout << ' ' << cur->key << " found\n";
    }
}

void free_tree(Node *node)
{
    if (node == nullptr) {
        return;
    }
    free_tree(node->left);
    free_tree(node->right);
    delete node; // (4)!
}

void inorder(Node *node)
{
    if (node == nullptr) {
        return;
    }
    inorder(node->left);
    cout << ' ' << node->key;
    inorder(node->right);
}

int main()
{
    int n, q;
    cin >> n;
    Node *root = nullptr;
    for (int i = 0; i < n; i++) {
        int key;
        cin >> key;
        root = insert(root, key);
    }
    cout << "inorder:";
    inorder(root);
    cout << '\n';
    cin >> q;
    for (int i = 0; i < q; i++) {
        int key;
        cin >> key;
        find_key(root, key);
    }
    free_tree(root);
    return 0;
}

ต้นไม้ว่าง node ใหม่เป็นรากเลย ฟังก์ชันคืนรากกลับไป คนเรียกจึงเขียน root = insert(root, key) ทุกครั้ง
เทียบแล้วเลือกทาง ถ้าทางนั้นว่างก็แขวน node ใหม่ไว้แล้วจบ ไม่งั้นเดินลงไปหนึ่งชั้น
เดินลงจนเจอคีย์หรือตกออกนอกต้นไม้ พิมพ์คีย์ที่ผ่านไว้ด้วยเพื่อดูทาง
คืนลูกก่อนพ่อ คือ postorder จากหน้า 26.2 ถ้า delete node ก่อน จะอ่าน node->right ไม่ได้อีก

7
165 152 176 149 158 171 180
2
171 160

inorder: 149 152 158 165 171 176 180
search 171: 165 176 171 found
search 160: 165 152 158 not found

หา 171 ผ่าน 165 กับ 176 ตามเส้นหนาในภาพ หา 160 ซึ่งไม่มี เดิน 165 ไปซ้ายเพราะน้อยกว่า ถึง 152 ไปขวาเพราะมากกว่า ถึง 158 ไปขวาแล้วตกออกนอกต้นไม้ ถ้าจะใส่ 160 ก็แขวนไว้เป็นลูกขวาของ 158 ตรงนั้นพอดี

ทั้งใส่และค้นหาใช้ก้าวไม่เกินความสูงของต้นไม้บวกหนึ่ง จึงเป็น O(h) เมื่อ h คือความสูง ต้นไม้ในภาพสูง 2 ทุกคำสั่งจบในสามก้าว

inorder ได้ค่าเรียง

บรรทัดแรกของผลลัพธ์คือ inorder ซึ่งออกมาเรียงจากน้อยไปมากทั้งที่ใส่ไปไม่เรียง เหตุผลมาจากกฎของ BST ตรงๆ inorder พิมพ์ต้นไม้ย่อยซ้ายทั้งหมดก่อน แล้วตัวเอง แล้วต้นไม้ย่อยขวา ทุกคีย์ทางซ้ายน้อยกว่าตัวเอง ทุกคีย์ทางขวามากกว่า และต้นไม้ย่อยแต่ละข้างก็พิมพ์ตัวเองเรียงด้วยเหตุผลเดียวกัน

นี่คือเหตุผลที่วน set ด้วย for แล้วได้ค่าเรียง และ iterator ของ set เดินไปตัวถัดไปทีละก้าวแบบที่เห็นในหน้า 20.1 ตัวถัดไปของโหนดหนึ่งใน inorder อยู่ในต้นไม้ย่อยขวา หรือถ้าไม่มี ก็อยู่ที่บรรพบุรุษตัวใดตัวหนึ่ง ไม่ได้อยู่ติดกันในหน่วยความจำแบบอาเรย์

ลบ

การลบต้องรักษากฎของ BST ไว้ หาโหนดที่จะลบก่อน แล้วแยกเป็นสามกรณีตามจำนวนลูก

ไม่มีลูก ลบทิ้งได้เลย
มีลูกตัวเดียว ให้ลูกตัวนั้นขึ้นมาแทนที่ ทั้งต้นไม้ย่อยของลูกยังอยู่ฝั่งเดิมของพ่อ กฎจึงยังถูก
มีลูกสองตัว ต้องหาคีย์มาแทนที่ที่ยังมากกว่าทุกคีย์ทางซ้ายและน้อยกว่าทุกคีย์ทางขวา คีย์นั้นคือคีย์ที่น้อยที่สุดในต้นไม้ย่อยขวา ซึ่งก็คือตัวถัดไปใน inorder หาได้โดยลงขวาหนึ่งก้าวแล้วลงซ้ายจนสุด ลอกคีย์นั้นมาใส่โหนดนี้ แล้วไปลบคีย์นั้นออกจากต้นไม้ย่อยขวา ซึ่งเป็นกรณีที่ 1 หรือ 2 เสมอ เพราะโหนดที่อยู่ซ้ายสุดไม่มีลูกซ้าย

เขียนเป็นฟังก์ชันที่รับรากของต้นไม้ย่อย แล้วคืนรากใหม่หลังลบ แบบเดียวกับ insert ข้างบน

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *left;
    Node *right;
};

Node *insert(Node *node, int key) // (1)!
{
    if (node == nullptr) {
        node = new Node;
        node->key = key;
        node->left = nullptr;
        node->right = nullptr;
    } else if (key < node->key) {
        node->left = insert(node->left, key);
    } else {
        node->right = insert(node->right, key);
    }
    return node;
}

Node *erase(Node *node, int key)
{
    if (node == nullptr) {
        return nullptr;
    }
    if (key < node->key) {
        node->left = erase(node->left, key);
        return node;
    }
    if (key > node->key) {
        node->right = erase(node->right, key);
        return node;
    }
    if (node->left == nullptr) { // (2)!
        Node *child = node->right;
        delete node;
        return child;
    }
    if (node->right == nullptr) {
        Node *child = node->left;
        delete node;
        return child;
    }
    Node *next = node->right; // (3)!
    while (next->left != nullptr) {
        next = next->left;
    }
    node->key = next->key;
    node->right = erase(node->right, next->key); // (4)!
    return node;
}

void preorder(Node *node)
{
    if (node == nullptr) {
        return;
    }
    cout << ' ' << node->key;
    preorder(node->left);
    preorder(node->right);
}

void free_tree(Node *node)
{
    if (node == nullptr) {
        return;
    }
    free_tree(node->left);
    free_tree(node->right);
    delete node;
}

int main()
{
    int n, q;
    cin >> n;
    Node *root = nullptr;
    for (int i = 0; i < n; i++) {
        int key;
        cin >> key;
        root = insert(root, key);
    }
    cout << "start:";
    preorder(root);
    cout << '\n';
    cin >> q;
    for (int i = 0; i < q; i++) {
        int key;
        cin >> key;
        root = erase(root, key);
        cout << "erase " << key << ':';
        preorder(root);
        cout << '\n';
    }
    free_tree(root);
    return 0;
}

insert แบบ recursion สั้นกว่าแบบลูปข้างบน ลงไปทางที่ถูกจนเจอที่ว่าง แล้วคืน node ใหม่ขึ้นมาให้พ่อเกี่ยวไว้ แต่ลึกเท่าความสูงของต้นไม้
กรณีที่ 1 กับ 2 รวมกันได้ ไม่มีลูกซ้ายก็ให้ลูกขวาขึ้นมาแทน ถ้าลูกขวาไม่มีด้วย ก็ได้ nullptr ขึ้นมาแทน ซึ่งคือลบใบทิ้ง
กรณีที่ 3 ลงขวาหนึ่งก้าว แล้วลงซ้ายจนสุด ได้คีย์ที่น้อยที่สุดในต้นไม้ย่อยขวา
ตอนนี้คีย์นั้นมีอยู่สองที่ ต้องลบตัวเดิมที่อยู่ข้างล่างทิ้ง

7
165 152 176 149 158 171 180
3
149 152 165

start: 165 152 149 158 176 171 180
erase 149: 165 152 158 176 171 180
erase 152: 165 158 176 171 180
erase 165: 171 158 176 180

พิมพ์แบบ preorder เพราะ preorder บอกรูปร่างของต้นไม้ได้ ตัวแรกคือราก ลบ 149 ซึ่งเป็นใบ หายไปเฉยๆ ลบ 152 ที่เหลือลูกตัวเดียวคือ 158 ทำให้ 158 ขึ้นมาเป็นลูกซ้ายของ 165 แทน ลบ 165 ที่เป็นรากและมีลูกสองตัว ตัวที่น้อยที่สุดทางขวาคือ 171 ได้ขึ้นมาเป็นรากใหม่ inorder ของต้นไม้สุดท้ายคือ 158 171 176 180 ยังเรียงอยู่ การลบก็เป็น O(h) เพราะเดินลงไปทางเดียวไม่เกินสองรอบ

ต้นไม้เอียง

ทุกคำสั่งเป็น O(h) แล้ว h ใหญ่แค่ไหน รูปร่างของ BST ขึ้นกับลำดับที่ใส่ล้วนๆ โปรแกรมนี้ใส่คีย์ตามลำดับที่อ่าน แล้วพิมพ์ความสูง โดยนับความลึกของ node ใหม่ระหว่างที่เดินลง ไม่ต้องท่องต้นไม้

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *left;
    Node *right;
};

int main()
{
    int n;
    cin >> n;
    Node *root = nullptr;
    int height = 0;
    for (int i = 0; i < n; i++) {
        Node *node = new Node;
        cin >> node->key;
        node->left = nullptr;
        node->right = nullptr;
        if (root == nullptr) {
            root = node;
            continue;
        }
        Node *cur = root;
        int depth = 1; // (1)!
        while (true) {
            if (node->key < cur->key) {
                if (cur->left == nullptr) {
                    cur->left = node;
                    break;
                }
                cur = cur->left;
            } else {
                if (cur->right == nullptr) {
                    cur->right = node;
                    break;
                }
                cur = cur->right;
            }
            depth++;
        }
        height = max(height, depth);
    }
    cout << "height " << height << '\n';
    return 0;
}

เริ่มที่ลูกของราก ซึ่งลึก 1 ทุกครั้งที่เดินลงอีกชั้นก็บวกหนึ่ง ตอนแขวน node ใหม่ depth คือความลึกของมันพอดี

7
1 2 3 4 5 6 7

height 6

ใส่ 1 ถึง 7 เรียงกันได้ความสูง 6 ทุกคีย์ใหม่มากกว่าทุกตัวที่มีอยู่ จึงไปต่อทางขวาของตัวล่าสุดเสมอ ต้นไม้กลายเป็นเส้นตรงที่เอียงไปทางขวา ซึ่งก็คือ linked list ดีๆ นี่เอง ถ้าใส่คีย์ชุดเดียวกันในลำดับ 4 2 6 1 3 5 7 จะได้ความสูง 2 เท่านั้น

7
4 2 6 1 3 5 7

height 2

ลองกับข้อมูลใหญ่ วัดบนเครื่องเดียวกับหน้า 19.1 คอมไพล์แบบ -O2 ใส่คีย์ 1 ถึง N ลงต้นไม้ที่เขียนเองแบบโปรแกรม shape กับลง set<int> สองแบบ คือเรียงจากน้อยไปมาก และสลับลำดับแบบสุ่ม รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

N	ลำดับที่ใส่	ความสูงของต้นไม้ที่เขียนเอง	ต้นไม้ที่เขียนเอง	set
1,000	สุ่ม	21	0.000 วินาที	0.000 วินาที
1,000	เรียงแล้ว	999	0.001 วินาที	0.000 วินาที
10,000	สุ่ม	34	0.001 วินาที	0.001 วินาที
10,000	เรียงแล้ว	9,999	0.091 วินาที	0.001 วินาที
100,000	สุ่ม	42	0.019 วินาที	0.018 วินาที
100,000	เรียงแล้ว	99,999	12.333 วินาที	0.010 วินาที
1,000,000	สุ่ม	46	0.610 วินาที	0.711 วินาที

อ่านได้สามเรื่อง

ถ้าลำดับที่ใส่สุ่มจริง ต้นไม้ที่เขียนเองสูงแค่ 21 ถึง 46 ไม่ถึง 3 เท่าของ log₂ N และเร็วพอๆ กับ set ที่ล้านตัวเร็วกว่าด้วย
ถ้าใส่ข้อมูลที่เรียงแล้ว ความสูงคือ N - 1 การใส่ตัวที่ k ต้องเดิน k ก้าว รวมเป็น O(N²) แสนตัวใช้สิบกว่าวินาที
set ไม่สนลำดับที่ใส่ เรียงแล้วเร็วกว่าสุ่มด้วยซ้ำ

โจทย์ที่ให้คีย์มาเรียงแล้วเจอบ่อยมาก เช่น เวลาที่เพิ่มขึ้นเรื่อยๆ หรือหมายเลขที่ไล่ 1 2 3 ชุดทดสอบที่ดีจึงมีข้อมูลเรียงอยู่เสมอ ส่วนการท่องต้นไม้ที่เอียงด้วย recursion ก็เจอปัญหาของหน้า 26.3 ด้วย บนเครื่องที่ทดลอง ป้อน 1 ถึง 50000 เรียงกันให้โปรแกรม bst ข้างบน แบบ Code::Blocks พังด้วย 0xC00000FD ทั้ง 3 ครั้งที่ลอง แบบ -O2 ผ่าน ซึ่งไม่ควรเอาไปเสี่ยงกับ grader

set ไม่เอียงเพราะอะไร

ต้นไม้ใน set คือ red-black tree ชื่อ _Rb_tree ที่เห็นในข้อความ error ของหน้า 20.1 เป็น BST แบบเดียวกับหน้านี้ แต่ทุกครั้งที่ใส่หรือลบ มันตรวจว่าต้นไม้เริ่มเอียงหรือยัง ถ้าเอียงก็ปรับรูปร่างด้วยการ หมุน (rotation) คือยกลูกขึ้นมาแทนพ่อ แล้วให้พ่อลงไปเป็นลูกแทน ภาพนี้คือการหมุนทางซ้ายครั้งเดียวที่เปลี่ยนเส้นตรง 1 2 3 ให้กลับมาสูง 1

หลังหมุน inorder ยังเป็น 1 2 3 เหมือนเดิม กฎของ BST จึงไม่เสีย red-black tree มีกติกาว่าเมื่อไรต้องหมุนที่ไหน ซึ่งรับประกันว่าความสูงไม่เกิน 2 log₂(N + 1) เสมอ แสนคีย์สูงไม่เกิน 34 ไม่ว่าจะใส่ในลำดับไหน ทุกคำสั่งจึงเป็น O(log N) จริง โค้ดของ red-black tree ยาวหลายร้อยบรรทัดและมีกรณีย่อยเยอะ ค่าย 2 และ TOI ไม่ได้คาดหวังให้เขียนเอง ให้ใช้ set กับ map ที่มีให้แล้ว

แล้ว BST ที่เขียนเองมีไว้ทำไม เรื่องแรก มันทำให้รู้ว่า set เร็วเพราะอะไร และทำไม iterator ของ set บวกเลขไม่ได้ เรื่องที่สอง โจทย์บางข้อถามถึงรูปร่างของ BST ที่ได้จากการใส่ตามลำดับ เช่น ความลึกของแต่ละคีย์ ซึ่ง set ไม่ได้ให้มา ต้องจำลองเอง แบบฝึกหัดข้อ 7 และข้อ 9 เป็นแบบนี้ ส่วนถ้าจำเป็นต้องเขียนเองและรู้คีย์ทั้งหมดก่อนแล้ว ให้สลับลำดับแบบสุ่มก่อนใส่ ต้นไม้จะเตี้ยแบบแถวสุ่มในตาราง

ลองทำให้พัง

แบบที่ 1 ลอกคีย์แล้วลืมลบตัวเดิม

ในโปรแกรม erase ลบบรรทัด node->right = erase(node->right, next->key); ออก เพราะคิดว่าลอกคีย์ขึ้นมาแล้วก็จบ

7
165 152 176 149 158 171 180
3
149 152 165

start: 165 152 149 158 176 171 180
erase 149: 165 152 158 176 171 180
erase 152: 165 158 176 171 180
erase 165: 171 158 176 171 180

สองครั้งแรกยังถูก เพราะเป็นกรณีที่ 1 กับ 2 พอลบ 165 ที่มีลูกสองตัว 171 ขึ้นมาเป็นราก แต่ 171 ตัวเดิมยังอยู่เป็นลูกซ้ายของ 176 ต้นไม้มี 171 สองตัว inorder จะได้ 158 171 171 176 180 บั๊กนี้ไม่พังและผ่านชุดทดสอบที่ลบแต่ใบ ให้ทดสอบการลบครบทั้งสามกรณีทุกครั้ง โดยเฉพาะการลบราก

แบบที่ 2 ใส่ข้อมูลที่เรียงแล้ว

ตารางข้างบนคือการทำให้พังแบบที่เจอบ่อยที่สุด ไม่มี error ไม่มี warning คำตอบถูกทุกตัว แค่ช้าจนเกินเวลา ถ้าต้องการแค่ค่าเรียง ค้นหา และลบ ให้ใช้ set ถ้าโจทย์บังคับให้จำลอง BST ตามลำดับที่ใส่ ให้ดูขอบเขตก่อน N หลักพันจำลองตรงๆ ได้ N หลักแสนต้องมีวิธีที่ไม่เดินลงทีละชั้น ซึ่งเป็นแบบฝึกหัดข้อ 9

สรุป

BST ทุกคีย์ทางซ้ายน้อยกว่า ทุกคีย์ทางขวามากกว่า ค้นหาด้วยการเลือกเลี้ยวซ้ายหรือขวาทีละชั้น
ใส่คือค้นหาจนตกที่ว่างแล้วแขวน node ใหม่ inorder ของ BST ได้คีย์เรียงจากน้อยไปมาก
ลบแยกสามกรณี ไม่มีลูกลบเลย ลูกเดียวให้ลูกขึ้นแทน สองลูกลอกคีย์ที่น้อยที่สุดทางขวามาแล้วลบตัวเดิม
ทุกคำสั่งเป็น O(h) ใส่คีย์สุ่มได้ h ไม่ถึง 3 log₂ N ใส่คีย์ที่เรียงแล้วได้ h = N - 1 แสนตัวใช้สิบกว่าวินาที
set กับ map เป็น red-black tree ที่หมุนตัวเองให้สูงไม่เกิน 2 log₂(N + 1) จึงไม่เอียงไม่ว่าใส่ลำดับไหน ใช้ตัวนี้เมื่อแค่ต้องการเก็บและค้นหา