平衡係数の取得

Coddyの「AVL Tree - データ構造シリーズ #10」コースのレッスン 6/16。

ノードの平衡係数は、getHeight(node.left) - getHeight(node.right) です。正の数は左側の方が高いことを意味し、負の数は右側の方が高いことを意味します。そして 0 はそれらが同じ高さであることを意味します。

平衡係数が -1、0、または 1 である限り、ノードは平衡であると見なされます。その範囲外（2 以上、または -2 以下）になると、回転がトリガーされます。

チャレンジ

初心者

AVLTree に getBalance(node) メソッドを記述してください。このメソッドは、node が null の場合は 0 を返し、それ以外の場合は getHeight(node.left) - getHeight(node.right) を返します。

自分で試してみよう

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