Hapus
Pelajaran 11 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.
Penghapusan adalah penghapusan BST dengan kebiasaan penyeimbangan ulang yang sama seperti penyisipan. Ada tiga bentuk yang perlu ditangani untuk node yang dihapus: tidak memiliki anak (cukup hapus node itu), memiliki satu anak (ganti node itu dengan anak tersebut), atau memiliki dua anak, kasus yang rumit, yaitu mengganti nilai node dengan penerus in-order (nilai terkecil di subtree kanannya), lalu menghapus penerus tersebut dari subtree kanan.
Sama seperti penyisipan, setiap leluhur saat kembali ke atas menghitung ulang tinggi dan faktor keseimbangannya, lalu menerapkan kasus rotasi yang sesuai jika node menjadi tidak seimbang. Logika penyeimbangan ulangnya identik dengan penyisipan, hanya saja kondisi untuk memilih kasus kini melihat faktor keseimbangan anak yang lebih berat, bukan lokasi nilai baru.
Tantangan
SedangTulis method delete(value) pada AVLTree (helper rekursif cocok digunakan). Hapus value dengan penghapusan BST standar: untuk node dengan dua anak, ganti nilainya dengan nilai terkecil di subtree kanannya, lalu hapus nilai tersebut dari subtree kanan. Jangan lakukan apa pun jika value tidak ditemukan. Saat naik kembali, hitung ulang tinggi dan seimbangkan kembali persis seperti yang dilakukan insert.
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, "delete") == 0) {
AVLTree_delete(tree, arg);
}
if (parsed >= 1 && strcmp(cmd, "search") == 0) {
if (AVLTree_search(tree, arg)) {
printf("true\n");
}
if (!AVLTree_search(tree, arg)) {
printf("false\n");
}
}
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");
}
}
return 0;
}
Semua pelajaran di Pohon AVL, Seri Struktur Data #10
Latihan sendiri: Compiler C online