จำนวนโหนดน้อยที่สุดในต้นไม้ AVL ที่มีความสูงกำหนดด้วย C++

ข้อความโจทย์

กำหนดความสูงของต้นไม้ AVL งานคือหาจำนวนโหนดน้อยที่สุดที่ต้นไม้นั้นสามารถมีได้

ถ้าความสูง = 0 ต้นไม้ AVL สามารถมี 1 โหนด
ถ้าความสูง = 5 ต้นไม้ AVL สามารถมีโหนดขั้นต่ำ 20 โหนด

อัลกอริทึม

ในต้นไม้ AVL เราต้องรักษาคุณสมบัติสมดุลความสูง (Height Balance Property) คือ ความแตกต่างของความสูงระหว่างต้นไม้ย่อยซ้ายและขวาไม่สามารถมากกว่า -1, 0 หรือ 1 สำหรับแต่ละโหนด โดยใช้คุณสมบัตินี้ เราสามารถสร้างความสัมพันธ์แบบเวียนเกิด (Recurrence Relation) ด้านล่างได้ -

1. ถ้าความสูง = 0 คืนค่า 1
2. ถ้าความสูง = 1 คืนค่า 2
3. ถ้าความสูง > 1 คืนค่า (1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h - 2))

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int getMinAVLNodes(int h) {
    if (h < 0) {
        return 0;
    }
    if (h == 0 || h == 1) {
        return h + 1;
    }
    return 1 + getMinAVLNodes(h - 1) + getMinAVLNodes(h - 2);
}

int main() {
    int h = 5;
    cout << "Minimum nodes for " << h << " height = " << getMinAVLNodes(h) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum nodes for 5 height = 20