ตรวจสอบว่า Binary Tree สมดุลแบบ Red-Black Tree หรือไม่ใน C++

แนวคิด

ใน Red-Black Tree ความสูงสูงสุดของโหนดไม่เกิน 2 เท่าของความสูงต่ำสุด สำหรับ Binary Search Tree ที่กำหนด ต้องตรวจสอบว่า: สำหรับทุกโหนด ความยาวเส้นทางจากโหนดไปยัง leaf ที่ไกลที่สุด ≤ 2 × เส้นทางที่สั้นที่สุด

วิธีการแก้ปัญหา

สำหรับแต่ละโหนด ต้องหาความสูงสูงสุด (maxh) และต่ำสุด (minh) แล้วเปรียบเทียบ ใช้ฟังก์ชัน recursive ที่คืนค่า 3 ค่า: boolean (สมดุลหรือไม่), maxh, minh โดยส่ง maxh, minh ด้วย reference เพื่อใช้ใน parent call

• Base case: NULL node → maxh = minh = 0, return true
• เรียก recursive ซ้ายและขวา
• maxh = max(lmxh, rmxh) + 1
• minh = min(lmnh, rmnh) + 1
• ถ้า maxh ≤ 2×minh → true มิฉะนั้น false

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

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

struct Node1{
    int key;
    Node1 *left, *right;
};

Node1* newNode(int key){ ... }

bool isBalancedUtil(Node1 *root, int &maxh1, int &minh1){
    if (root == NULL){
        maxh1 = minh1 = 0;
        return true;
    }
    int lmxh1, lmnh1;
    int rmxh1, rmnh1;
    if (isBalancedUtil(root->left, lmxh1, lmnh1) == false)
        return false;
    if (isBalancedUtil(root->right, rmxh1, rmnh1) == false)
        return false;
    maxh1 = max(lmxh1, rmxh1) + 1;
    minh1 = min(lmnh1, rmnh1) + 1;
    if (maxh1 <= 2*minh1)
        return true;
    return false;
}

bool isBalanced(Node1 *root){
    int maxh1, minh1;
    return isBalancedUtil(root, maxh1, minh1);
}

int main(){
    Node1 * root = newNode(11);
    root->left = newNode(6);
    root->right = newNode(101);
    root->right->left = newNode(51);
    root->right->right = newNode(151);
    root->right->left->left = newNode(41);
    isBalanced(root)? cout << "Balanced" : cout << "Not Balanced";
    return 0;
}

ผลลัพธ์

Balanced