קבלת גורם האיזון
שיעור 6 מתוך 16 בקורס עץ AVL – סדרת מבני נתונים מס' 10 של Coddy.
גורם האיזון של צומת הוא getHeight(node.left) - getHeight(node.right). מספר חיובי פירושו שהצד השמאלי גבוה יותר, מספר שלילי פירושו שהצד הימני גבוה יותר, ו־0 פירושו שהם שווים.
צומת נחשב מאוזן כל עוד גורם האיזון שלו הוא -1, 0 או 1. כל ערך מחוץ לטווח הזה (2 או יותר, או -2 או פחות) הוא זה שמפעיל סיבוב.
אתגר
מתחיליםכתבו מתודה getBalance(node) במחלקה AVLTree שמחזירה 0 אם node הוא null, אחרת מחזירה 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;
}
כל השיעורים ביחידה עץ AVL – סדרת מבני נתונים מס' 10
2פרויקט עץ AVL
מחלקת צומתמחלקת AVLTreeתרגלו בעצמכם: קומפיילר C אונליין