균형 인수 구하기

Coddy의 AVL 트리 - 자료구조 시리즈 #10 코스 레슨 — 16개 중 6번째.

노드의 균형 인수(balance factor)는 getHeight(node.left) - getHeight(node.right)입니다. 양수는 왼쪽이 더 높음을 의미하고, 음수는 오른쪽이 더 높음을 의미하며, 0은 양쪽의 높이가 같음을 의미합니다.

노드의 균형 인수가 -1, 0 또는 1인 경우 해당 노드는 균형이 잡힌 것으로 간주됩니다. 이 범위를 벗어나는 값(2 이상 또는 -2 이하)은 회전(rotation)을 유발합니다.

챌린지

초급

AVLTree에 node가 null이면 0을 반환하고, 그렇지 않으면 getHeight(node.left) - getHeight(node.right)를 반환하는 getBalance(node) 메서드를 작성하세요.

직접 해보기

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