Kiểm tra cây nhị phân cân bằng như cây Đỏ-Đen (Red-Black Tree) trong C++

Khái niệm

Trong cây Đỏ-Đen, chiều cao lớn nhất của một nút không vượt quá gấp đôi chiều cao nhỏ nhất. Cho cây tìm kiếm nhị phân, kiểm tra tính chất: với mọi nút, đường đi dài nhất từ nút đến lá không quá 2 lần đường đi ngắn nhất.

Ví dụ minh họa (cây cân bằng và không cân bằng).

Yêu cầu độ phức tạp O(n), duyệt cây tối đa một lần.

Phương pháp

Với mỗi nút, tính chiều cao lớn nhất (maxh) và nhỏ nhất (minh) của các cây con. Nút cân bằng nếu maxh <= 2*minh. Hàm đệ quy trả về 3 giá trị: boolean cân bằng, maxh, minh (truyền tham chiếu).

Ví dụ (C++)

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

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

Node1* newNode(int key){
    Node1* node1 = new Node1;
    node1->key = key;
    node1->left = node1->right = NULL;
    return node1;
}

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

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;
}

Đầu ra

Balanced