"Halo, Amigo!"
"Hallo, Riska!"
"Aku nemokake cathetan lawas ing kana lan nyiapake sawetara materi sing menarik kanggo sampeyan. Aku mikir sampeyan bakal kasengsem krungu."
"Ayo dirungokake. Sampeyan mesthi nemokake sing menarik sing mengko bukti banget migunani."
"Oke. Dina iki aku arep nyritakake babagan wit , mula aku bakal miwiti nganggo grafik ."
" Grafik yaiku sistem titik lan garis sing nyambungake. Titik kasebut diarani verteks grafik, lan garis kasebut diarani pinggiran grafik. Contone:"
"Grafik trep banget kanggo digunakake minangka model matématika kanggo macem-macem proses lan tugas ing donya nyata. Akeh tugas lan algoritma sing beda-beda wis diciptakake kanggo grafik, mula asring digunakake."
"Contone, umpamane vertices minangka kutha, lan pinggiran minangka dalan. Banjur nggoleki dalan sing paling cedhak antarane kutha dadi: «diwenehi grafik, golek dalan paling cedhak antarane rong vertices» .
"Nanging path saka A kanggo B ora tansah padha path saka B kanggo A. Dadi, kadhangkala duwe loro garis beda luwih disenengi. Kanggo nindakake iki, garis (pinggiran saka grafik) diganti karo panah. Ing tembung liyane, grafik bisa duwe rong panah: siji saka A menyang B, lan liyane saka B kanggo A."
"Yen grafik kasebut nggunakake panah, mula diarani grafik terarah ; yen mung ana garis, mula diarani grafik sing ora diarahake ."
"Saben vertex bisa duwe nomer pinggiran dhewe-dhewe. A vertex uga bisa ora duwe pinggiran kabeh. Kosok baline, vertex bisa disambungake dening sudhut kanggo saben vertex liyane. Yen saben pasangan vertex ing grafik disambungake dening pinggiran, banjur Iki diarani grafik lengkap. "
"Yen sampeyan bisa nggunakake pinggiran kanggo nggayuh saben vertex ing grafik, banjur diarani graph disambungake . A graph sing duwe telung vertex kapisah lan ora ana pinggiran isih graph, nanging kita nelpon graph pedhot ."
"Kanggo mbentuk grafik sing disambungake saka N vertex, sampeyan kudu paling sethithik N-1 pinggiran. Jinis grafik iki diarani wit."
"Apamaneh, biasane siji vertex dipilih dadi oyod wit , lan liyane diumumake minangka cabang. Pange wit sing ora duwe pange dhewe diarani godhong . Contone:"
"Yen saben unsur saka wit duwe anak loro, banjur diarani wit binar . Ing tembung liyane, bisa uga ana 0 utawa 2 cabang. Sampeyan bisa ndeleng wit binar ing sisih tengen ndhuwur."
" Wit diarani wit biner lengkap yen saben cabang duwe anak 2, lan kabeh godhong (vertices tanpa anak) ana ing baris sing padha."
"Tuladhane:"
"Napa wit-witan iki dibutuhake?"
"Oh, wit digunakake ing akeh panggonan. Umumé, wit binar diurutake data terstruktur."
"Apa iku?"
"Ya, iku gampang banget. Kita nyimpen nilai tartamtu ing saben vertex. Lan saben unsur nderek aturan: nilai sing disimpen ing anak tengen kudu luwih gedhe tinimbang nilai sing disimpen ing vertex, lan nilai sing disimpen ing anak kiwa kudu kurang saka nilai sing disimpen ing vertex. Pesenan iki bisa kanthi cepet nemokake unsur wit sing sampeyan butuhake."
"Apa sampeyan bisa njlentrehake apa tegese?"
"Unsur wit biasane diurutake kanthi nambah. Upaminipun kita duwe 7 unsur: 13, 5, 4, 16, 8, 11, 10"
"Iki carane unsur ditambahake ing wit."
"Yen kita nggoleki nomer 7 ing wit iki, mula iki bakal ditindakake."
"0) Mulai ing ROOT.
"1a) Apa 7 padha karo 13? Ora"
"1b) Apa 7 luwih gedhe tinimbang 13? Ora, dadi pindhah menyang subtree kiwa.
"2a) Apa 7 padha karo 5? Ora."
"2b) Apa 7 luwih gedhe tinimbang 5? Ya, supaya kita pindhah menyang subtree tengen."
"3a) Apa 7 padha karo 8? Ora"
"3b) Apa 7 luwih gedhe tinimbang 8? Ora, dadi pindhah menyang subtree kiwa.
"4a) Ora ana subtree kiwa, tegese angka 7 ora ana ing wit kasebut."
"Ah. Ing tembung liyane, kita mung perlu mriksa vertex ing path saka ROOT menyang lokasi bakal-bakal nomer sing dikarepake. Ya, sing tenan cepet."
"Apa maneh yen wit kasebut seimbang, sampeyan mung kudu ngliwati 20 simpul kanggo nggoleki sejuta unsur."
"Aku setuju - sing ora akeh banget."
"Apa tegese wit imbang?"
"Wit sing ora kleru, yaiku sing ora duwe cabang sing dawa. Contone, yen unsur-unsur kasebut wis diurut nalika kita mbangun wit kasebut, mula kita bakal nggawe wit sing dawa banget sing dumadi saka siji cabang. "
"Hmm. Sampeyan bener. Dadi apa sing kudu ditindakake?"
"Minangka sampeyan wis bisa ngira, wit sing paling efisien duwe cabang sing kira-kira dawane padha. Banjur saben perbandingan mbuwang bagean paling gedhe saka subtree sing isih ana."
"Dadi, kita kudu mbangun maneh wit kasebut?"
"Yep. Iku kudu «imbang» - kanggo digawe minangka cedhak wit binar lengkap.
"Kanggo ngatasi masalah iki, wit timer imbangan nemokke. Yen wit dadi kleru sawise nambah unsur, banjur reorders unsur rada kanggo nggawe kabeh OK. Punika conto imbangan: "
"Sawetara wit iki dikenal minangka wit abang -ireng ."
"Yagene dheweke diarani abang-ireng?"
"Penemu dheweke nggambar kabeh simpul nggunakake rong warna. Siji werna abang, lan liyane ireng. Pucuk sing beda manut aturan sing beda. Iki dadi basis kabeh prosedur imbangan."
"Tuladhane:"
"Dadi apa aturan iki?"
"1) Pucuk abang ora bisa dadi anak saka pucuk abang."
"2) Jero ireng saben rwaning padha (jero ireng nuduhake jumlah verteks ireng ing dalan saka oyod)."
"3) Oyod wit iku ireng."
"Aku ora bakal nerangake carane iki bisa - sampeyan sirah mbokmenawa wis njeblug."
"Iya. Prosesorku ngetokke asap sithik."
"Iki link kanggo sampeyan. Yen sampeyan pengin, sampeyan bisa maca liyane babagan kene."
"Lan saiki, ayo ngaso."
GO TO FULL VERSION