Sisipkan
Pelajaran 9 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.
insert dimulai seperti penyisipan biasa pada pohon pencarian biner: telusuri pohon sambil membandingkan nilai, bergerak ke kiri atau ke kanan, lalu tempatkan node baru di posisi kosong yang bernilai null (abaikan duplikat). Bagian AVL terjadi saat menelusuri kembali ke atas: setelah node ditempatkan, setiap leluhur pada jalur tersebut menghitung ulang height dan memeriksa faktor keseimbangannya.
Jika sebuah node menjadi tidak seimbang, sisi mana yang lebih berat dan di mana nilai baru ditempatkan menentukan kasus mana dari empat kasus yang berlaku: kiri-kiri dan kanan-kanan memerlukan satu rotasi, sedangkan kiri-kanan dan kanan-kiri memerlukan dua rotasi, yaitu rotasi bagian dalam untuk meluruskan pola zig-zag, lalu rotasi bagian luar.
Tantangan
SedangTulis method insert(value) pada AVLTree (helper rekursif adalah cara yang paling rapi). Sisipkan value seperti pada BST biasa, abaikan jika sudah ada. Saat kembali ke atas, hitung ulang tinggi dan faktor keseimbangan setiap node. Jika sebuah node tidak seimbang, terapkan rotasi yang sesuai (atau sepasang rotasi) sebelum kembali ke atas tumpukan pemanggilan.
Coba sendiri
#include <stdio.h>
#include <string.h>
#include "avltree.h"
static void preorderValues(Node* node, int* vals, int* count) {
if (node == NULL) {
return;
}
vals[(*count)++] = node->value;
preorderValues(node->left, vals, count);
preorderValues(node->right, vals, count);
}
int main(void) {
AVLTree* tree = AVLTree_create();
char line[256];
while (fgets(line, sizeof(line), stdin) != NULL) {
line[strcspn(line, "\r\n")] = '\0';
char cmd[32];
int arg;
int parsed = sscanf(line, "%31s %d", cmd, &arg);
if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
AVLTree_insert(tree, arg);
}
if (parsed >= 1 && strcmp(cmd, "preorder") == 0) {
int vals[10000];
int count = 0;
preorderValues(tree->root, vals, &count);
for (int i = 0; i < count; i++) {
if (i > 0) {
printf(" ");
}
printf("%d", vals[i]);
}
printf("\n");
}
if (parsed >= 1 && strcmp(cmd, "height") == 0) {
printf("%d\n", AVLTree_getHeight(tree, tree->root));
}
}
return 0;
}
Semua pelajaran di Pohon AVL, Seri Struktur Data #10
Latihan sendiri: Compiler C online