26.3 ต้นไม้ลึกกับ stack ที่เขียนเอง

โปรแกรมในหน้า 26.2 สั้นและถูกต้อง แต่ทุกตัวใช้ recursion ที่ลึกเท่าความสูงของต้นไม้ หน้า 9.1 วัดไว้ว่า sum_to ลึกได้ราวสี่หมื่นสามพันชั้นก่อน stack จะเต็ม ส่วนโจทย์ต้นไม้ในค่าย 2 และ TOI มีโหนดเป็นแสน และชุดทดสอบมักมีต้นไม้ที่เป็นเส้นตรงยาวทั้งต้น หน้านี้วัดว่าโปรแกรมท่องต้นไม้ลึกได้กี่ชั้นจริง แล้วเปลี่ยนเป็นลูปที่ใช้ stack ของเราเอง ซึ่งลึกเท่าไรก็ไม่พัง

ลึกได้กี่ชั้น

โปรแกรมนี้นับขนาดของต้นไม้ย่อยแบบหน้า 26.2 ตัดให้เหลือแค่พิมพ์รากกับขนาดของทั้งต้น

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

vector<int> children[1000001]; // (1)!
int subtree_size[1000001];

void count_size(int v)
{
    subtree_size[v] = 1;
    for (int c : children[v]) {
        count_size(c);
        subtree_size[v] += subtree_size[c];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int root = 0;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> p;
        if (p == 0) {
            root = i;
        } else {
            children[p].push_back(i);
        }
    }
    count_size(root);
    cout << "root " << root << " size " << subtree_size[root] << '\n';
    return 0;
}

1. อาเรย์ของ vector ประกาศไว้นอก main ล้านช่อง จะได้ใช้ข้อมูลชุดใหญ่ทดลองได้ vector ว่างแต่ละตัวกิน 24 byte รวมราว 24 MB ซึ่งอยู่นอก stack จึงไม่ติดขีดจำกัด 2 MB ของตัวแปรใน main

9
0 1 1 2 2 3 1 5 7

root 1 size 9

ป้อนต้นไม้เส้นตรง N โหนด โหนด 1 เป็นราก และพ่อของโหนด v คือ v - 1 การเรียก count_size จะลึก N ชั้น บนเครื่องที่ทดลอง รันจาก PowerShell ค่า 25,000 ถึง 29,000 ค่าละ 10 ครั้ง ค่าอื่นค่าละ 3 ครั้ง ได้ผลดังนี้

ทุกครั้งที่พังได้

Process returned -1073741571 (0xC00000FD)

stack overflow เหมือนหน้า 9.1 ลึกได้ราวสองหมื่นห้าพันชั้น น้อยกว่า sum_to ที่ได้สี่หมื่นสามพัน เพราะแต่ละชั้นต้องจำมากกว่า ทั้งโหนดปัจจุบัน และตำแหน่งที่วนลูกไปถึงแล้ว stack ราว 2 MB หารด้วยสองหมื่นหกพันชั้น ได้ชั้นละราว 80 byte และต่างจาก sum_to ที่ -O2 ทำให้ลึกได้เป็นร้อยล้าน ตัวนี้แบบ -O2 พังที่ความลึกเกือบเท่ากับแบบ Code::Blocks

โจทย์ต้นไม้ส่วนใหญ่ให้ N ถึงแสนหรือสองแสน ถ้าชุดทดสอบมีเส้นตรงยาวขนาดนั้น โปรแกรมแบบนี้ได้ runtime error แน่นอน grader บางที่ตั้ง stack ไว้ใหญ่กว่าเครื่องเรา บางที่ไม่ อย่าเสี่ยง ใช้หลักเดียวกับหน้า 9.1 คือ recursion ที่ลึกได้ถึงหลักหมื่นชั้นขึ้นไปให้เขียนเป็นลูป

preorder ด้วย stack ของเราเอง

recursion ทำงานได้เพราะ call stack จำไว้ว่ายังมีโหนดไหนค้างอยู่ ถ้าเราจำเองใน stack<int> จากบทที่ 17 ซึ่งเก็บของไว้ในหน่วยความจำที่ขอระหว่างรันเหมือน vector ก็ไม่ติดขีดจำกัด 2 MB อีกต่อไป

เริ่มด้วยใส่รากลง stack แล้ววน หยิบโหนดบนสุดออกมา จดไว้ แล้วใส่ลูกของมันลง stack ลูกที่ใส่ทีหลังจะถูกหยิบก่อน ถ้าอยากได้ลำดับเดียวกับ preorder แบบ recursion ที่ไปลูกตัวแรกก่อน ต้องใส่ลูกจากตัวสุดท้ายย้อนมาหาตัวแรก

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

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> children(n + 1);
    int root = 0;
    for (int v = 1; v <= n; v++) {
        int p;
        cin >> p;
        if (p == 0) {
            root = v;
        } else {
            children[p].push_back(v);
        }
    }
    vector<int> order;
    stack<int> waiting;
    waiting.push(root);
    while (!waiting.empty()) {
        int v = waiting.top(); // (1)!
        waiting.pop();
        order.push_back(v);
        for (int i = (int)children[v].size() - 1; i >= 0; i--) { // (2)!
            waiting.push(children[v][i]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << order[i];
    }
    cout << '\n';
    return 0;
}

1. โหนดบนสุดของ stack คือโหนดที่ recursion จะไปเป็นตัวถัดไป หยิบออกแล้วจดได้เลย
2. วนจากลูกตัวสุดท้ายย้อนกลับ ลูกตัวแรกจึงอยู่บนสุดและถูกหยิบก่อน ต้อง cast size() เป็น int ก่อนลบ 1 ไม่งั้นโหนดที่ไม่มีลูกจะได้ 0 - 1 แบบไม่มีเครื่องหมาย ซึ่งเป็นเลขใหญ่มาก

9
0 1 1 2 2 3 1 5 7

1 2 4 5 8 3 6 7 9

ได้ 1 แล้วลงไปทั้งกิ่งของ 2 คือ 2 4 5 8 ก่อนจะไป 3 6 และ 7 9 เป็น preorder ตรงกับที่ recursion ให้ ทุกโหนดเข้าและออกจาก stack ครั้งเดียว ยังเป็น O(N) และ stack ของเราลึกได้เท่ากับหน่วยความจำที่เหลือ ต้นไม้เส้นตรงล้านโหนดก็แค่ล้านช่อง

postorder ด้วยการย้อนลำดับ

งานในหน้า 26.2 ส่วนใหญ่ เช่น ขนาด ความสูง ผลรวมของต้นไม้ย่อย ต้องการลำดับที่ลูกเสร็จก่อนพ่อ การเขียน postorder ด้วย stack โดยตรงต้องจำว่าแต่ละโหนดทำลูกไปถึงตัวไหนแล้ว ยุ่งกว่ามาก มีทางที่ง่ายกว่า

ใน preorder พ่อมาก่อนลูกเสมอ ถ้าเดินลำดับนี้ย้อนจากท้ายมาหน้า ลูกก็มาก่อนพ่อเสมอ พอถึงโหนด v ลูกทุกตัวของ v ถูกทำไปหมดแล้ว ส่งคำตอบของ v ขึ้นไปรวมที่พ่อได้ทันที โดยใช้ parent ที่อ่านมาอยู่แล้ว

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> parent(n + 1);
    vector<vector<int>> children(n + 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);
        }
    }
    vector<int> order;
    stack<int> waiting;
    waiting.push(root);
    while (!waiting.empty()) {
        int v = waiting.top();
        waiting.pop();
        order.push_back(v);
        for (int c : children[v]) { // (1)!
            waiting.push(c);
        }
    }
    vector<int> subtree_size(n + 1, 1), height(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) { // (2)!
        int v = order[i];
        int p = parent[v];
        if (p != 0) { // (3)!
            subtree_size[p] += subtree_size[v];
            height[p] = max(height[p], height[v] + 1);
        }
    }
    for (int v = 1; v <= n; v++) {
        cout << "node " << v << " size " << subtree_size[v] << " height " << height[v] << '\n';
    }
    return 0;
}

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

9
0 1 1 2 2 3 1 5 7

node 1 size 9 height 3
node 2 size 4 height 2
node 3 size 2 height 1
node 4 size 1 height 0
node 5 size 2 height 1
node 6 size 1 height 0
node 7 size 2 height 1
node 8 size 1 height 0
node 9 size 1 height 0

ตรงกับโปรแกรม measure ในหน้า 26.2 ทุกบรรทัด ป้อนต้นไม้เส้นตรงล้านโหนด บรรทัดแรกได้ node 1 size 1000000 height 999999 ไม่พัง

ลำดับจาก level order ในหน้า 26.2 ก็ใช้แบบเดียวกันได้ เพราะพ่อออกจากคิวก่อนลูกเสมอ ขอแค่ลำดับที่พ่อมาก่อนลูก จะได้มาจาก stack หรือ queue ก็ได้ ส่วนเส้นผ่านศูนย์กลางก็เปลี่ยนแบบเดียวกัน ตอนทำ v ให้เอา height[v] + 1 ไปอัปเดตค่ามากสุดสองอันดับแรกของพ่อ

เมื่อพ่อมีหมายเลขน้อยกว่าลูกเสมอ

บางโจทย์รับประกันว่าพ่อของโหนด v มีหมายเลขน้อยกว่า v เช่น บอกพ่อของโหนด 2 ถึง N ตามลำดับ และพ่อของโหนด v อยู่ระหว่าง 1 ถึง v - 1 กรณีนี้หมายเลขโหนดเองเป็นลำดับที่พ่อมาก่อนลูกแล้ว ไม่ต้องสร้าง children และไม่ต้องมี stack เลย

for (int v = n; v >= 2; v--) {
    subtree_size[parent[v]] += subtree_size[v];
}

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

ช้ากว่า recursion ไหม

วัดบนเครื่องเดียวกับหน้า 19.1 คำนวณขนาดและความสูงของทุกต้นไม้ย่อย N = 1,000,000 โหนด ต้นไม้สุ่มสูง 32 กับต้นไม้เส้นตรง จับเวลาเฉพาะส่วนที่คำนวณ ฝั่งวนด้วย stack รวมการสร้าง order ด้วย รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

ทั้งสองแบบเป็น O(N) เวลาจึงอยู่ระดับเดียวกัน แบบ -O2 ซึ่งเป็นแบบที่ grader ใช้ วนด้วย stack เร็วกว่าเล็กน้อยด้วยซ้ำ ส่วนแบบ Code::Blocks ช้ากว่า recursion ราวหนึ่งในสาม สิ่งที่ต่างจริงคือบรรทัดเส้นตรง แบบหนึ่งพัง อีกแบบเสร็จในเวลาไม่ถึงหนึ่งในสิบวินาที

inorder ด้วย stack

binary tree ที่ต้องการ inorder จริงๆ เช่น ต้นไม้ค้นหาในหน้า 26.4 ที่อาจเอียงเป็นเส้นตรง ต้องจดโหนดหลังจากทำต้นไม้ย่อยซ้ายเสร็จ เขียนด้วย stack ได้ด้วยการเลียนแบบ recursion ตรงๆ เดินลงซ้ายสุดพร้อมกับใส่ทุกโหนดที่ผ่านลง stack เพราะยังต้องกลับมาจดมัน พอไปต่อไม่ได้ หยิบโหนดบนสุดออกมาจด แล้วไปทำต้นไม้ย่อยขวาของมันด้วยวิธีเดิม

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

int main()
{
    int n;
    cin >> n;
    vector<string> token(n + 1);
    vector<int> left_child(n + 1), right_child(n + 1);
    for (int v = 1; v <= n; v++) {
        cin >> token[v] >> left_child[v] >> right_child[v];
    }
    vector<string> visited;
    stack<int> waiting;
    int v = 1;
    while (v != 0 || !waiting.empty()) {
        while (v != 0) { // (1)!
            waiting.push(v);
            v = left_child[v];
        }
        v = waiting.top(); // (2)!
        waiting.pop();
        visited.push_back(token[v]);
        v = right_child[v]; // (3)!
    }
    for (int i = 0; i < (int)visited.size(); i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << visited[i];
    }
    cout << '\n';
    return 0;
}

1. ลงซ้ายจนสุด ทุกโหนดที่ผ่านยังจดไม่ได้ เพราะต้นไม้ย่อยซ้ายของมันยังไม่เสร็จ จึงพักไว้ใน stack
2. โหนดบนสุดคือโหนดที่ต้นไม้ย่อยซ้ายเสร็จแล้ว ถึงตาจดมัน
3. ทำต้นไม้ย่อยขวาต่อ ถ้าไม่มี v จะเป็น 0 รอบถัดไปจึงข้ามการลงซ้าย แล้วหยิบโหนดที่พักไว้ตัวถัดไป

9
/ 2 7
+ 3 4
8 0 0
* 5 6
2 0 0
5 0 0
- 8 9
6 0 0
4 0 0

8 + 2 * 5 / 6 - 4

ได้บรรทัด inorder เดียวกับหน้า 26.2 ทุกโหนดเข้าและออกจาก stack ครั้งเดียว เป็น O(N)

ลองทำให้พัง

แบบที่ 1 ใส่ลูกลง stack ตามลำดับปกติ

ในโปรแกรม stack-preorder เปลี่ยนลูปใส่ลูกเป็น for (int i = 0; i < (int)children[v].size(); i++) ซึ่งดูเป็นธรรมชาติกว่า

9
0 1 1 2 2 3 1 5 7

1 7 9 3 6 2 5 8 4

ยังไปครบทุกโหนด และพ่อยังมาก่อนลูก แต่พี่น้องกลับลำดับหมด 7 มาก่อน 3 ซึ่งมาก่อน 2 เพราะลูกตัวสุดท้ายถูกใส่ทีหลังสุดจึงถูกหยิบก่อน ถ้าโจทย์ให้พิมพ์ preorder ตามลำดับลูกที่กำหนด คำตอบนี้ผิด ถ้าแค่ต้องการลำดับที่พ่อมาก่อนลูกเพื่อเอาไปย้อน แบบนี้ใช้ได้ ซึ่งก็คือที่โปรแกรม bottom-up ทำ

แบบที่ 2 ไม่ย้อนลำดับ

ในโปรแกรม bottom-up เปลี่ยนลูปส่งค่าขึ้นพ่อเป็น for (int i = 0; i < n; i++)

9
0 1 1 2 2 3 1 5 7

node 1 size 4 height 1
node 2 size 3 height 1
node 3 size 2 height 1
node 4 size 1 height 0
node 5 size 2 height 1
node 6 size 1 height 0
node 7 size 2 height 1
node 8 size 1 height 0
node 9 size 1 height 0

รากได้ขนาด 4 แทนที่จะเป็น 9 ลำดับใน order คือ 1 7 9 3 6 2 5 8 4 แบบเดียวกับผลของแบบที่ 1 พอเดินไปข้างหน้า โหนด 7 ถูกทำก่อนโหนด 9 ซึ่งเป็นลูกของมัน จึงส่งค่าเริ่มต้น 1 ขึ้นไปให้รากก่อนที่ 9 จะส่งมาถึง โหนด 3 กับ 2 ก็เหมือนกัน รากจึงได้ 1 + 1 + 1 + 1 = 4 ไม่มี error ไม่มีอะไรพัง มีแต่ตัวเลขผิด กฎคือคำตอบของ v จะส่งขึ้นไปได้ก็ต่อเมื่อลูกทุกตัวของ v ส่งมาครบแล้ว ลำดับย้อนของ preorder รับประกันข้อนี้ ลำดับไปข้างหน้าไม่รับประกัน

สรุป

• recursion ท่องต้นไม้บนเครื่องที่ทดลองลึกได้ราวสองหมื่นห้าพันชั้น ต้นไม้เส้นตรงแสนโหนดพังด้วย 0xC00000FD ทั้งแบบ Code::Blocks และ -O2
• preorder ด้วย stack<int> ใส่ลูกจากตัวสุดท้ายย้อนมา จะได้ลำดับเดียวกับ recursion
• งานที่ลูกต้องเสร็จก่อนพ่อ ให้เก็บลำดับที่พ่อมาก่อนลูกไว้ แล้วเดินย้อนจากท้าย ส่งค่าขึ้นไปที่ parent
• ถ้าโจทย์รับประกันว่าพ่อมีหมายเลขน้อยกว่าลูก วน v จาก N ลงมาได้เลย
• inorder ด้วย stack คือลงซ้ายสุดพร้อมพักโหนดไว้ หยิบมาจด แล้วไปทางขวา
• วนด้วย stack ใช้เวลา O(N) เท่ากับ recursion และไม่พังกับต้นไม้ลึกเท่าไรก็ได้