26.1 ต้นไม้และการเก็บในโปรแกรม

ข้อมูลทุกแบบที่ผ่านมาเรียงเป็นแถว ไม่ว่าจะเป็นอาเรย์ linked list หรือตาราง แต่ของหลายอย่างในชีวิตจริงเป็นลำดับชั้น ผังโรงเรียนมีผู้อำนวยการอยู่บนสุด ใต้ลงมาเป็นรองผู้อำนวยการ หัวหน้ากลุ่มสาระ แล้วจึงเป็นครู โฟลเดอร์ในเครื่องมีโฟลเดอร์ย่อยซ้อนลงไปเรื่อยๆ สายตระกูลมีพ่อแม่ ลูก และหลาน โครงสร้างแบบนี้เรียกว่า ต้นไม้ (tree) และ set map priority_queue ในบทที่ 20 ก็เป็นต้นไม้อยู่ข้างใน หน้านี้เริ่มจากคำศัพท์ที่โจทย์ใช้ แล้วดูสามวิธีเก็บต้นไม้ในโปรแกรม พร้อมวิธีอ่านต้นไม้จากข้อมูลเข้า ซึ่งเป็นสิ่งแรกที่ต้องทำในโจทย์ต้นไม้ทุกข้อ

ต้นไม้คืออะไร

ต้นไม้ประกอบด้วย โหนด (node) ซึ่งก็คือของแต่ละชิ้น เช่น คนหนึ่งคนในผังโรงเรียน กับ เส้นเชื่อม (edge) ระหว่างโหนดที่เป็นหัวหน้ากับลูกน้องโดยตรง กติกามีสามข้อ

• มีโหนดเดียวที่อยู่บนสุด เรียกว่า ราก (root)
• ทุกโหนดที่ไม่ใช่รากมีโหนดเหนือตัวเองโดยตรงหนึ่งโหนดพอดี
• เริ่มจากโหนดไหนก็ตาม เดินขึ้นไปเรื่อยๆ แล้วจะถึงรากเสมอ ไม่มีทางวนกลับมาที่เดิม

ต้นไม้ในวิชาคอมพิวเตอร์วาดรากไว้ข้างบนและแตกกิ่งลงล่าง กลับหัวกับต้นไม้จริง ภาพนี้คือชมรมหุ่นยนต์ของโรงเรียนที่มีสมาชิก 9 คน หมายเลข 1 ถึง 9 แต่ละเส้นต่อจากหัวหน้าลงไปหาคนที่รายงานตรงต่อคนนั้น

คำศัพท์ที่โจทย์ใช้

โจทย์ต้นไม้เขียนด้วยคำเหล่านี้ทั้งนั้น อ่านตารางคู่กับภาพข้างบน

ข้อเท็จจริงที่ใช้บ่อยมาก ต้นไม้ที่มี N โหนดมีเส้นเชื่อม N - 1 เส้นพอดี เพราะทุกโหนดยกเว้นรากมีเส้นขึ้นไปหาพ่อของตัวเองหนึ่งเส้น ภาพข้างบนมี 9 โหนดและ 8 เส้น โจทย์จำนวนมากจึงบอกแค่ว่า "มี N - 1 บรรทัด แต่ละบรรทัดบอกเส้นเชื่อมหนึ่งเส้น" แล้วให้เรารู้เองว่าเป็นต้นไม้

binary tree

ต้นไม้ที่ทุกโหนดมีลูกได้ไม่เกินสองตัว และแยกชัดว่าตัวไหนเป็นลูกซ้าย (left child) ตัวไหนเป็นลูกขวา (right child) เรียกว่า binary tree (ต้นไม้ทวิภาค) โหนดที่มีลูกตัวเดียวก็ต้องบอกว่าอยู่ทางซ้ายหรือทางขวา สองแบบนี้ถือเป็นคนละต้นไม้กัน ต้นไม้ค้นหาในหน้า 26.4 และ heap ในหน้า 26.5 เป็น binary tree ทั้งคู่

โหนด 1 ไม่มีลูกซ้าย มีแต่ลูกขวาคือ 4 ถ้าย้าย 4 ไปเป็นลูกซ้ายของ 1 จะได้ binary tree อีกต้นหนึ่ง ตัวเลขในวงกลมเป็นแค่หมายเลขประจำโหนด ไม่ได้บอกลำดับอะไร ต่อไปจะเก็บต้นไม้ต้นนี้ในโปรแกรมสองแบบ

แบบที่ 1 node กับ pointer

แบบตรงไปตรงมาที่สุดคือทำเหมือน linked list ในหน้า 14.1 แต่ละ node มี pointer สองตัวไปหาลูกซ้ายกับลูกขวา ขอ node ใหม่ด้วย new และคืนด้วย delete ตามหน้า 15.5

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

struct Node {
    int value;
    Node *left; // (1)!
    Node *right;
};

Node *make_node(int value)
{
    Node *node = new Node;
    node->value = value;
    node->left = nullptr; // (2)!
    node->right = nullptr;
    return node;
}

int main()
{
    Node *root = make_node(3);
    root->left = make_node(1);
    root->right = make_node(6);
    root->left->right = make_node(4); // (3)!
    root->right->left = make_node(2);
    root->right->right = make_node(5);
    cout << "root " << root->value << '\n';
    cout << "left of root " << root->left->value << '\n';
    cout << "right of root " << root->right->value << '\n';
    cout << "right of " << root->left->value << " is " << root->left->right->value << '\n';
    if (root->left->left == nullptr) {
        cout << root->left->value << " has no left child\n";
    }
    delete root->right->right; // (4)!
    delete root->right->left;
    delete root->left->right;
    delete root->right;
    delete root->left;
    delete root;
    return 0;
}

1. linked list มี next ตัวเดียว node ของ binary tree มีทางไปต่อสองทาง
2. nullptr คือยังไม่มีลูกทางนั้น ต้องตั้งเองทุกครั้ง new ไม่ได้ตั้งให้ เหมือนกับดักเรื่อง next ของตู้สุดท้ายในหน้า 14.1
3. เดินตาม pointer สองทอด จากราก ไปลูกซ้าย แล้วตั้งลูกขวาของโหนดนั้น
4. คืนลูกก่อนพ่อ ถ้าคืนพ่อก่อน จะอ่าน root->right หลังจากที่ root ถูกคืนไปแล้วไม่ได้ หน้า 26.4 จะเขียนฟังก์ชันคืนทั้งต้นไม้ให้

root 3
left of root 1
right of root 6
right of 1 is 4
1 has no left child

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

แบบที่ 2 อาเรย์ลูกซ้ายกับลูกขวา

โจทย์แข่งขันส่วนใหญ่ให้โหนดมีหมายเลข 1 ถึง N อยู่แล้ว เหมือนนักเรียนหมายเลข 1 ถึง N ในหน้า 14.3 จึงใช้หมายเลขเป็น index ได้เลย เก็บลูกซ้ายของโหนด v ไว้ที่ left[v] ลูกขวาที่ right[v] และใช้ 0 แทน "ไม่มีลูก" เหมือนที่ 0 แทน NULL ในหน้า 14.3

ข้อมูลเข้าของโจทย์แบบนี้มักเป็น บรรทัดแรกคือ N แล้วอีก N บรรทัด บรรทัดที่ v บอกลูกซ้ายและลูกขวาของโหนด v โดยไม่บอกว่ารากคือโหนดไหน ต้องหาเอง รากคือโหนดเดียวที่ไม่ได้เป็นลูกของใครเลย

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

int main()
{
    int n;
    cin >> n;
    vector<int> left(n + 1), right(n + 1); // (1)!
    vector<bool> has_parent(n + 1, false);
    for (int v = 1; v <= n; v++) {
        cin >> left[v] >> right[v];
        has_parent[left[v]] = true; // (2)!
        has_parent[right[v]] = true;
    }
    int root = 0;
    for (int v = 1; v <= n; v++) {
        if (!has_parent[v]) { // (3)!
            root = v;
        }
    }
    cout << "root " << root << '\n';
    for (int v = 1; v <= n; v++) {
        if (left[v] == 0 && right[v] == 0) {
            cout << "leaf " << v << '\n';
        }
    }
    return 0;
}

1. ขอ n + 1 ช่องแล้วไม่ใช้ช่อง 0 หมายเลขโหนดจะตรงกับ index พอดี
2. โหนดที่ไม่มีลูกซ้ายจะได้ left[v] เป็น 0 บรรทัดนี้จึงไปตั้ง has_parent[0] ด้วย ไม่เสียหาย เพราะช่อง 0 มีอยู่จริงและเราไม่เคยดูมัน
3. โหนดที่ไม่มีใครชี้มาหาคือราก ต้นไม้ที่ถูกต้องมีแบบนี้โหนดเดียว

6
0 4
0 0
1 6
0 0
0 0
2 5

root 3
leaf 2
leaf 4
leaf 5

บรรทัดที่สามของข้อมูลเข้าคือโหนด 3 มีลูกซ้าย 1 ลูกขวา 6 ตรงกับภาพ แบบอาเรย์ได้ข้อดีเดียวกับลิสต์ด้วยอาเรย์ในหน้า 14.3 ทุกข้อ ไม่ต้อง new ไม่ต้อง delete พิมพ์ข้างในออกมาดูง่าย และกระโดดไปหาโหนดหมายเลข v ได้ทันที คนแข่งจึงใช้แบบนี้เป็นหลัก

แบบที่ 3 รายชื่อลูกด้วย vector

ต้นไม้ทั่วไปอย่างชมรมหุ่นยนต์ แต่ละโหนดมีลูกได้ไม่จำกัด จะเปิดอาเรย์ left right ไม่ได้แล้ว ให้แต่ละโหนดมี vector ของลูกตัวเอง children[v] ยาวเท่าไรก็ได้ตามจำนวนลูก

รูปแบบข้อมูลเข้าที่พบบ่อยที่สุดของต้นไม้ทั่วไปคือบอกพ่อของแต่ละโหนด บรรทัดแรกคือ N บรรทัดที่สองมี N ตัว ตัวที่ v คือพ่อของโหนด v และรากมีพ่อเป็น 0 ชมรมหุ่นยนต์เขียนได้แบบนี้

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

int main()
{
    int n;
    cin >> n;
    vector<int> parent(n + 1);
    vector<vector<int>> children(n + 1); // (1)!
    int root = 0;
    for (int v = 1; v <= n; v++) {
        cin >> parent[v];
        if (parent[v] == 0) {
            root = v;
        } else {
            children[parent[v]].push_back(v); // (2)!
        }
    }
    cout << "root " << root << '\n';
    for (int v = 1; v <= n; v++) {
        cout << "node " << v << ':';
        if (children[v].empty()) {
            cout << " leaf";
        }
        for (int c : children[v]) {
            cout << ' ' << c;
        }
        cout << '\n';
    }
    return 0;
}

1. vector ของ vector แบบตารางในหน้า 16.2 แต่ละแถวยาวไม่เท่ากัน เริ่มต้นทุกแถวว่าง
2. รู้พ่อของ v แล้ว ก็ใส่ v ลงในรายชื่อลูกของพ่อ อ่านข้อมูลรอบเดียวได้รายชื่อลูกครบทุกโหนด

9
0 1 1 2 2 3 1 5 7

root 1
node 1: 2 3 7
node 2: 4 5
node 3: 6
node 4: leaf
node 5: 8
node 6: leaf
node 7: 9
node 8: leaf
node 9: leaf

ลูกในแต่ละแถวเรียงตามลำดับที่อ่านเจอ ซึ่งก็คือเรียงตามหมายเลข เพราะเราไล่ v จาก 1 ถึง N ทั้งหมดใช้เวลา O(N) และเนื้อที่ O(N) เพราะทุกโหนดอยู่ในรายชื่อลูกของพ่อแค่ครั้งเดียว

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

หาความลึกด้วยการเดินขึ้น

มีพ่อของทุกโหนดอยู่แล้ว ความลึกของโหนด v ก็คือจำนวนก้าวที่เดินจาก v ขึ้นไปจนถึงราก

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

int main()
{
    int n;
    cin >> n;
    vector<int> parent(n + 1);
    for (int v = 1; v <= n; v++) {
        cin >> parent[v];
    }
    int height = 0;
    for (int v = 1; v <= n; v++) {
        int depth = 0;
        for (int u = v; parent[u] != 0; u = parent[u]) { // (1)!
            depth++;
        }
        cout << "depth of " << v << " is " << depth << '\n';
        height = max(height, depth);
    }
    cout << "height " << height << '\n';
    return 0;
}

1. เดินขึ้นทีละก้าวแบบเดินตาม next ในลิสต์ หยุดเมื่อถึงโหนดที่ไม่มีพ่อ ซึ่งก็คือราก

9
0 1 1 2 2 3 1 5 7

depth of 1 is 0
depth of 2 is 1
depth of 3 is 1
depth of 4 is 2
depth of 5 is 2
depth of 6 is 2
depth of 7 is 1
depth of 8 is 3
depth of 9 is 2
height 3

ถูกต้องทุกโหนด และเขียนสั้นมาก แต่ลองคิดว่าใช้กี่ก้าว โหนด v ใช้ก้าวเท่ากับความลึกของมัน รวมทั้งหมดจึงเป็นผลรวมความลึกของทุกโหนด ถ้าต้นไม้แตกกิ่งเยอะ ความลึกแต่ละโหนดน้อย ก็เร็ว แต่ถ้าต้นไม้เป็นเส้นตรง โหนด 1 เป็นพ่อของ 2 โหนด 2 เป็นพ่อของ 3 ไปเรื่อยๆ ผลรวมคือ 0 + 1 + ... + (N - 1) ราว N²/2 ก้าว เป็น O(N²) หน้า 26.2 จะวัดให้ดูว่า N แสนตัวช้าแค่ไหน และหาความลึกทุกโหนดใน O(N)

ลองทำให้พัง

แบบที่ 1 รากมีพ่อเป็น -1

บางโจทย์ใช้ -1 แทน "ไม่มีพ่อ" แทนที่จะใช้ 0 ถ้าลืมตรวจและใส่ทุกโหนดลงในรายชื่อลูกของพ่อทันที แบบนี้

for (int v = 1; v <= n; v++) {
    cin >> parent[v];
    children[parent[v]].push_back(v);
}

ป้อนชมรมหุ่นยนต์ที่เปลี่ยนพ่อของรากเป็น -1 1 1 2 2 3 1 5 7 คอมไพล์ผ่านโดยไม่มีคำเตือน แต่บนเครื่องที่ทดลอง รันจาก PowerShell ทั้งแบบ Code::Blocks และ -O2 แบบละ 5 ครั้ง โปรแกรมปิดตัวทุกครั้งโดยไม่พิมพ์อะไรเลย

Process returned -1073741819 (0xC0000005)

children[-1] คือช่องก่อนช่องแรกของ vector ซึ่งไม่มีอยู่จริง push_back ไปเขียนหน่วยความจำที่ไม่ใช่ของเรา ผลแบบนี้ไม่แน่นอน เครื่องอื่นอาจพังที่จุดอื่นหรือไม่พังแต่ได้คำตอบผิด 0xC0000005 คือรหัสเดียวกับการอ่าน NULL->value ในบทที่ 14 ถ้าโจทย์ใช้ 0 แทนไม่มีพ่อ โค้ดนี้จะไม่พัง เพราะช่อง 0 มีอยู่จริง แต่รากจะไปอยู่ในรายชื่อลูกของโหนด 0 ซึ่งต้องจำไว้ว่าไม่ใช่โหนดจริง ทางที่ปลอดภัยคือตรวจกรณีรากแยกไว้เสมอแบบโปรแกรม children

แบบที่ 2 เดาว่ารากคือโหนด 1

ตัวอย่างในโจทย์หลายข้อบังเอิญมีรากเป็นโหนด 1 คนจึงเขียนเริ่มจากโหนด 1 เลยโดยไม่หาราก แล้วผ่านตัวอย่าง แต่ชุดทดสอบอาจสลับหมายเลขโหนดไว้ ในโปรแกรม array-tree ถ้าตัดส่วนที่หารากทิ้งแล้วถือว่า root = 1 binary tree ข้างบนจะเริ่มเดินจากโหนด 1 ซึ่งเป็นแค่ต้นไม้ย่อยที่มีโหนด 1 กับ 4 ส่วนโหนด 3 6 2 5 หายไปทั้งหมด ไม่มี error ไม่มี warning มีแต่คำตอบผิด ถ้าโจทย์ไม่ได้รับประกันว่ารากคือโหนดไหน ให้หาเองทุกครั้ง

สรุป

• ต้นไม้มีรากหนึ่งโหนด ทุกโหนดอื่นมีพ่อหนึ่งโหนด N โหนดมี N - 1 เส้น
• ความลึกนับเส้นจากรากลงมา ความสูงนับเส้นจากโหนดลงไปถึงใบที่ไกลที่สุด ตรวจในโจทย์ว่านับเส้นหรือนับโหนด
• binary tree มีลูกซ้ายและลูกขวาแยกกัน เก็บด้วย pointer สองตัว หรืออาเรย์ left[] right[] ที่ใช้ 0 แทนไม่มีลูก
• ต้นไม้ทั่วไปเก็บเป็น vector<vector<int>> children สร้างจากพ่อของแต่ละโหนดได้ในรอบเดียว
• รากคือโหนดที่ไม่มีพ่อ หาเองทุกครั้งถ้าโจทย์ไม่ได้บอก และตรวจกรณีรากแยกก่อนใช้พ่อเป็น index
• เดินขึ้นหารากทีละโหนดใช้เวลาเท่าความลึก ต้นไม้ที่เป็นเส้นตรงทำให้รวมแล้วเป็น O(N²)