Leluhur Bersama Terendah
Pelajaran 14 dari 16 dalam kursus Pohon AVL, Seri Struktur Data #10 di Coddy.
ancestor bersama terendah dari dua nilai adalah node terdalam yang memiliki keduanya di suatu tempat dalam subtree-nya. Dalam binary search tree, kamu dapat menemukannya tanpa pernah membandingkan subtree secara langsung: mulai dari root, jika kedua nilai lebih kecil daripada node saat ini, jawabannya ada di suatu tempat di subtree kiri; jika keduanya lebih besar, jawabannya ada di subtree kanan.
Saat kedua nilai berada di sisi yang berbeda (atau salah satunya sama dengan node saat ini), kamu telah menemukan titik pemisah: node itu adalah ancestor bersama terendah.
Tantangan
MudahTulis fungsi lca(tree, p, q) yang mengembalikan nilai leluhur bersama terendah dari p dan q. Kamu dapat mengasumsikan bahwa kedua nilai tersebut ada di dalam pohon.
Coba sendiri
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"
int main(void) {
AVLTree* tree = AVLTree_create();
char line1[4096];
fgets(line1, sizeof(line1), stdin);
char* tok = strtok(line1, " \n");
while (tok != NULL) {
AVLTree_insert(tree, atoi(tok));
tok = strtok(NULL, " \n");
}
char line2[256];
fgets(line2, sizeof(line2), stdin);
int p0 = atoi(strtok(line2, " \n"));
int p1 = atoi(strtok(NULL, " \n"));
int result = lca(tree, p0, p1);
printf("%d\n", result);
return 0;
}
Semua pelajaran di Pohon AVL, Seri Struktur Data #10
3Tantangan Latihan
Elemen Terkecil ke-KJumlah RentangLeluhur Bersama TerendahPenelusuran Berdasarkan Urutan LevelPenerus Suatu NilaiLatihan sendiri: Compiler C online