Ambil Faktor Keseimbangan

Pelajaran 6 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.

Faktor keseimbangan sebuah node adalah getHeight(node.left) - getHeight(node.right). Angka positif berarti sisi kiri lebih tinggi, angka negatif berarti sisi kanan lebih tinggi, dan 0 berarti keduanya sama tinggi.

Sebuah node dianggap seimbang selama faktor keseimbangannya adalah -1, 0, atau 1. Nilai di luar rentang tersebut (2 atau lebih, atau -2 atau kurang) akan memicu rotasi.

Tantangan

Pemula

Tulis method getBalance(node) pada AVLTree yang mengembalikan 0 jika node bernilai null, jika tidak, mengembalikan getHeight(node.left) - getHeight(node.right).

Coba sendiri

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

Semua pelajaran di Pohon AVL, Seri Struktur Data #10

1Pengantar

Pengantar Apa itu Pohon AVL?

2Proyek AVL Tree

Class Node Class AVLTree

Ambil Tinggi

Ambil Faktor Keseimbangan Pelajaran proyek

3Tantangan Latihan

Elemen Terkecil ke-K Jumlah Rentang Leluhur Bersama Terendah Penelusuran Berdasarkan Urutan Level Penerus Suatu Nilai

Latihan sendiri: Compiler C online