Balanced binary tree là gì?

Cây nhị phân cân bằng (balanced binary tree) còn được gọi là cây nhị phân cân bằng chiều cao (height-balanced binary tree), được định nghĩa là cây nhị phân (binary tree) trong đó chênh lệch chiều cao (height) của cây con bên trái (left subtree) và bên phải (right subtree) của bất kỳ nút (node) nào khác nhau không quá 1. Chiều cao của cây là số cạnh trên đường đi dài nhất giữa nút gốc (root node) và nút lá (leaf node).

Sau đây là các điều kiện cho cây nhị phân cân bằng (balanced binary tree):

• Sự khác biệt giữa cây con bên trái và bên phải cho bất kỳ nút nào không nhiều hơn một
• Cây con bên trái là cân bằng
• Cây con bên phải là cân bằng

Đoạn mã sau dùng để kiểm tra xem cây có cân bằng hay không trong ngôn ngữ C.

// Checking if a binary tree is height balanced in C

#include 
#include 
#define bool int

// Node creation
struct node {
  int item;
  struct node *left;
  struct node *right;
};

// Create a new node
struct node *newNode(int item) {
  struct node *node = (struct node *)malloc(sizeof(struct node));
  node->item = item;
  node->left = NULL;
  node->right = NULL;

  return (node);
}

// Check for height balance
bool checkHeightBalance(struct node *root, int *height) {
  // Check for emptiness
  int leftHeight = 0, rightHeight = 0;
  int l = 0, r = 0;

  if (root == NULL) {
    *height = 0;
    return 1;
  }

  l = checkHeightBalance(root->left, &leftHeight);
  r = checkHeightBalance(root->right, &rightHeight);

  *height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;

  if ((leftHeight - rightHeight >= 2) || (rightHeight - leftHeight >= 2))
    return 0;

  else
    return l && r;
}

int main() {
  int height = 0;

  struct node *root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
  root->left->right = newNode(5);

  if (checkHeightBalance(root, &height))
    printf("The tree is balanced");
  else
    printf("The tree is not balanced");
}