Cari
Pelajaran 10 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.
Karena tree ini selalu merupakan binary search tree yang valid (penyeimbangan tidak pernah merusak urutannya), pencarian di dalamnya sama persis seperti pencarian pada BST biasa: mulai dari root, lalu di setiap node bergerak ke kiri jika target lebih kecil, ke kanan jika lebih besar, atau berhenti jika cocok. Mencapai pointer null berarti nilainya tidak ada di dalam tree.
Karena penyeimbangan menjaga tinggi tree tetap sekitar log(n) tanpa memedulikan urutan nilai dimasukkan, pencarian ini tidak pernah berubah menjadi pemindaian linear yang lambat, tidak seperti BST yang tidak seimbang dan dibangun dari input terurut.
Tantangan
PemulaTulis method search(value) pada AVLTree yang mengembalikan true jika value ada di mana saja dalam tree, dan false jika tidak.
Coba sendiri
#include <stdio.h>
#include <string.h>
#include "avltree.h"
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, "search") == 0) {
if (AVLTree_search(tree, arg)) {
printf("true\n");
}
if (!AVLTree_search(tree, arg)) {
printf("false\n");
}
}
}
return 0;
}
Semua pelajaran di Pohon AVL, Seri Struktur Data #10
Latihan sendiri: Compiler C online