Menu
CoddyTech

Lấy hệ số cân bằng

Bài học 6 trên 16 trong khóa học Cây AVL, chuỗi cấu trúc dữ liệu #10 của Coddy.

Hệ số cân bằng của một nút là getHeight(node.left) - getHeight(node.right). Số dương nghĩa là phía trái cao hơn, số âm nghĩa là phía phải cao hơn, còn 0 nghĩa là hai bên bằng nhau.

Một nút được xem là cân bằng khi hệ số cân bằng của nó là -1, 0 hoặc 1. Bất kỳ giá trị nào ngoài phạm vi đó (2 trở lên hoặc -2 trở xuống) sẽ kích hoạt phép xoay.

challenge icon

Thử thách

Người mới

Viết phương thức getBalance(node) trong AVLTree, trả về 0 nếu node là null, nếu không thì trả về getHeight(node.left) - getHeight(node.right).

Tự làm thử

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "avltree.h"

static Node* mkNodeWithHeight(int h) {
    Node* n = Node_create(0);
    n->height = h;
    return n;
}

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        char lTok[64];
        char rTok[64];
        sscanf(line, "%63s %63s", lTok, rTok);
        Node* root = Node_create(0);
        root->left = NULL;
        if (strcmp(lTok, "null") != 0) {
            root->left = mkNodeWithHeight(atoi(lTok));
        }
        root->right = NULL;
        if (strcmp(rTok, "null") != 0) {
            root->right = mkNodeWithHeight(atoi(rTok));
        }
        printf("%d\n", AVLTree_getBalance(tree, root));
    }
    return 0;
}

Tất cả bài học trong Cây AVL, chuỗi cấu trúc dữ liệu #10

Tự luyện tập: Trình biên dịch C online