---
title: Skaldi un valdi, koki
image: https://www.sciencemag.org/sites/default/files/styles/article_main_image_-_1280w__no_aspect_/public/cc_iStock-478639870_16x9.jpg
description: Par to kādi notikumi attīstījās matemātikā un datorzinātnē līdz tika izgudrots B-koks.
tags: divide and conquer, decrease and conquer, binary tree, binary search tree, self balanced binary search tree, avl tree, b-tree
GA: G-6QHNFLGNM1
---

Skaldi un valdi, koki
===

Datorzinātne nav pēkšņi parādījies fenomens. Tā dziļi sakņojas vēsturē līdz pat 4000 gadu p.m.ē. Arheoloģiskie izrakumi uz māla plāksnītēm parāda kādas matemātiskās darbības un algoritmus zināja senajā Babilonijā. Šaja topikā par to kādi notikumi attīstījās matemātikā un datorzinātnē līdz tika izgudrots B-koks.

_Tags: divide and conquer, decrease and conquer, binary tree, binary search tree, self balanced binary search tree, avl tree, b-tree._

## Džataka par Losaku

<span style="font-family: inherit;">Topika ievadā fragments no “</span>[Džataka stāstiem](https://en.wikipedia.org/wiki/Jataka_tales)<span style="font-family: inherit;">” (senie budistu raksti, ap 4 gs. p.m.ē). Tulkots no </span>[avota](https://l.facebook.com/l.php?u=https%3A%2F%2Fwww.oum.ru%2Fliterature%2Fbuddizm%2Fdgataki-oglavlenie%2F%3Ffbclid%3DIwAR3G_KR7cVEwEbiOfHjBVSLyTVTKzCoz8S3Qf_L69mcOE1tOL6khcLe899c&h=AT1Nt2FYfDE384MpP4GPvGA_yCC4WZ7RzwDC19_TcuQvWD-6e2Z_yBwLL5wPmrmY94A-EwhFI17z1TpQzXCu0-FF5vmZWOwo-R92iKOB_7XzBq24d25ibaMeMKtjJw) krievu valodā (stāsts Nr. 41).

> Ja jautāsiet: "Kas ir Losaka Tissa?" - tad ziniet, Losaka, zvejnieka dēls, kurš dzīvoja Kosalas valstībā, bija savas cilts iznīcinātājs. Tūlīt pēc savas nāves, viņš pārdzima zvejnieces krūtī, kura dzīvoja Kosalas karalistes zvejas ciemā. Bez zvejnieces ģimenes ciemā dzīvoja arī citas ģimenes - kopā tūkstotis, kuras piederēja arī pie zvejnieku cilts. Tajā dienā, kad zvejniece ieņēma Losaku, visi ciema iedzīvotāji ar tīkliem rokās gāja zvejot: kāds uz upi, kāds uz dīķi un kāds kaut kur citur, bet neviens nenoķēra nevienu - pat vismazāko zivi. No tās dienas zvejniekiem gāja ar vien sliktāk un sliktāk. Un tad viņi sāka prātot: "Iepriekš viss bija labi, tagad kļūst sliktāk un sliktāk. Noteikti starp mums ir parādījies kāds, kurš nes nelaimi. Sadalīsimies!" Un sāka viņi dzīvot atsevišķi divās grupās: pieci simti ģimeņu vadīja paši savu saimniecību, otri pieci simti - savu. Un tā puse, kurā bija Losakas vecāki gāja nabadzībā, bet otrai pusei lietas padevās labi. Un tad viņi nolēma nabadzīgo pusi sadalīt vēlreiz uz pusēm, un darīja to tik daudz reižu, līdz viena ģimene izcēlās no pārējām. Kļuva skaidrs, ka šī ģimene ir nelaimju cēlonis un visi, kuri piederēja šai ģimenei tika sasisti un patriekti no ciema.

Šī ir vissenākā norāde (ko man izdevās atrast) uz algoritmu, kurš mūsdienās plaši tiek izmantots datorzinātnē. Kāds algoritms dotajā antīkajā piemērā tika pielietots un kur tas tiek pielietots datorzinātnē tiksim skaidrībā šajā topikā.

Zvejnieku ciema iemītnieki pielietoja [dihotomisko meklēšanu](https://l.facebook.com/l.php?u=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDichotomic_search%3Ffbclid%3DIwAR0bW_CP7o_xVmBDpuVtawyzlaLn8H0uDnq2Gm6FS2BcFUEx3rNEeTWkr3c&h=AT1Nt2FYfDE384MpP4GPvGA_yCC4WZ7RzwDC19_TcuQvWD-6e2Z_yBwLL5wPmrmY94A-EwhFI17z1TpQzXCu0-FF5vmZWOwo-R92iKOB_7XzBq24d25ibaMeMKtjJw) (_dichotomic search_) un, pēc mūsdienu klasifikācijas, pielietoto algoritmu var pieskaitīt pie “samazini un valdi” (_decrease and conquer_) algoritmu paradigmas.

Bez “samazini un valdi” algoritmu paradigmas, apskatīsim līdzīgu paradigmu, sauktu par “[skaldi un valdi](https://l.facebook.com/l.php?u=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FDivide-and-conquer_algorithm%3Ffbclid%3DIwAR2ju6IAgZ1CVprfp3_fct7mwREa-26SogHGjQA8KQR9xCBIxf0VjM0hrNw&h=AT1vUWsJK8BSLBLCsYACsJFAtle_7QQ_mSpzu-5BK5nOK3--0E-mpJ0X_lsFUZgVkS5k8oh8layL-B_N_GX4Rwq2F2Cqv57bXo4KzcS9ttZFhEAo0Hj1bOy_g7waDDl2-3dN796-gGoM5g) _divide and conquer_, ko lielākoties daudzi ir dzirdējuši kā militāru stratēģiju vai kā principu politikā un socioloģijā, bet mazāk dzirdēts ir par šo stratēģiju matemātikā un datorzinātnē.

## <span style="font-family: inherit;">Skaldi un valdi </span><span style="font-family: inherit;">(</span>_divide and conquer_<span style="font-family: inherit;">)</span>

<span style="font-family: inherit;">Algoritmi, kurus var raksturot ar skaldi un valdi principu darbojas sekojoši. Viena liela problēma (</span>_problem_<span style="font-family: inherit;">) tiek sadalīta (</span>_split_<span style="font-family: inherit;">) apakšproblēmās (</span>_subproblem_<span style="font-family: inherit;">) un tās tiek risinātas katra atsevišķi kā jauna problēma. Apakšproblēmas var tikt risinātas tiešā veidā vai arī, ja nepieciešams, tās var tikt risinātas, pielietojot to pašu skaldi un valdi stratēģiju līdz vienkāršam bāzes gadījumam (</span>_base case_<span style="font-family: inherit;">), kas noved pie rekursīvas struktūras. Atrisinot katru apakšproblēmu, rezultāti tiek apvienoti (</span>_merge_<span style="font-family: inherit;">) vienā risinājumā sākotnējai problēmai. Tā kā apakšproblēmas var tikt risinātas neatkarīgi, tad to risinājumus ir iespējams izskaitļoti vienlaicīgi (</span>_concurrency_<span style="font-family: inherit;">).</span>

<br/>


<br/>

Apskatīsim piemēru no loģistikas. Pastnieka ofisā atrodas 1000 vēstules, kuras jānogādā adresātiem Rīgā divos mikrorajonos. Pastnieka pārvietošanās līdzeklis ir velosipēds un vienā reizē viņš var līdzi paņemt ne vairāk kā 250 vēstules. Lai nogādātu visas vēstules līdz adresātiem, sanāk 4 reizes braukt uz ofisu. Neefektīvi būtu, ja vienā braukšanas reizē tiks paņemtas līdzi 250 vēstules, kuras atlasītas pēc nejaušības principa. Tad vēstuļu piegāde būtu ilgstoša, jo var sanākt braukt uz vienu un to pašu vietu vairākas reizes. Tāpēc pastnieks visas 1000 vētules sadala kaudzītēs, grupējot pēc mikrorajona. Kaudzītes tiek sadalītas vēl mazākās partijās, grupējot pēc apakšreģiona un pēc tam tiek izplānots visefektīvākais vēstuļu piegādes maršruts.


Iespējams jautāsiet, kur šeit ir apakšrisinājumu apvienošana? Dotajā piemērā nav, jo apvienošanas fāze nav nepieciešama, ja problēmu var uzskatīt par atrisinātu tad, kad visas apakšproblēmas ir atrisinātas. Kā nākamo, apskatīsim piemēru, kurā tiek izmantota apvienošanas fāze.

## Kārtošana ar sapludināšanu (_merge sort_)

<span></span>1945. gadā - laikā, kad tika pabeigts darbs pie pirmā vispārējas nozīmes datora ([ENIAC](https://en.wikipedia.org/wiki/ENIAC)) un pirmās detonētās atombumbas ([Trinity](https://en.wikipedia.org/wiki/Trinity_(nuclear_test))) - brīnumbērns [Džons fon Neimans](https://en.wikipedia.org/wiki/John_von_Neumann) izgudroja datu kārtošanas algoritmu sauktu par “*merge sort*”. 1944. gada vasarā Džons fon Neimans tika iesaistīts ENIAC datora izstrādē kā zinātniskais konsultants. Pēc ENIAC nepilnību analīzes viņš ierosināja uzbūvēt pilnīgāku datoru ([EDVAC](https://en.wikipedia.org/wiki/EDVAC)). Neimans rokrakstā uz 23 lapām uzrakstīja “*merge sort*” algoritma programmu priekš EDVAC. Šī programma tika klasificēta kā slepena militārā informācija. Vēlāk, 1970. gadā, amerikāņu datorzinātnieks un profesors [Donalds Knuts](https://en.wikipedia.org/wiki/Donald_Knuth) uzrakstīja darbu “[*Von Neumann’s First Computer Program*](http://public.callutheran.edu/~reinhart/CSC521MSCS/Week5/KnuthVonNeumann.pdf)”, kurā tika analizēta Neimana rakstītā programma.

Kārtošana ar sapludināšanu ir ļoti labs piemērs skaldi un valdi principa pielietojumam. Piemēram, lai sakārtotu augošā secībā skaitļu virkni 14,7,3,12,9,11,6,2, tad shematiski algoritmu var attēlot sekojoši.


Būtiski saprast, kas notiek apvienošanas fāzē. Piemēram, kā tiek sapludināti masīvi 3,7,12,14 un 2,6,9,11.


## Samazini un valdi (_decrease and conquer_)

Samazini un valdi no skaldi un valdi algoritmiem atšķiras ar to, ka sadalot problēmu mazākās instancēs, tās visas nav nepieciešams atrisināt. Piemēram, ja problēma tiek sadalīta divās instancēs, tad vienu no tām var risināt tālāk, bet otru atmest. Tādā veidā problēma tiek reducēta uz mazāku problēmu.

Ir sekojoši reducēšanas varianti:

* Samazināt pēc nemainīga lieluma (decrease by a constant amount)
* Samazināt pēc nemainīga koeficienta (decrease by a constant factor)
* Mainīgā izmēra samazināšana (variable size decrease)

#### Samazināšana pēc nemainīga koeficienta (decrease by a constant factor)

Katrā iterācijā problēma tiek reducēta pēc nemainīga koeficienta. Parasti koeficients ir 1/2, kas nozīmē, ka problēma tiek dalīta uz 2 - viena puse tiek risināta tālāk, otra puse atmesta. Ļoti retos gadījumos koeficients ir cits. Piemēram, šis variants tiek pielietos sekojošos algoritmos:

* [Binārmeklēšana](https://en.wikipedia.org/wiki/Binary_search_algorithm) (_binary search_)
* [Līdzsvara mīkla](https://en.wikipedia.org/wiki/Balance_puzzle) (_balance puzzle_)

## Binārmeklēšana (_binary search_)

Pirmā elektroniskā vispārējas nozīmes datora ENIAC izstrāde notika slepenībā no 1943. līdz 1945. gadam Pensilvānijas Universitātes [Mūra elektroinženierijas skolā](https://en.wikipedia.org/wiki/Moore_School_of_Electrical_Engineering) divu amerikāņu zinātnieku [Dž. V. Mouklija](https://en.wikipedia.org/wiki/John_Mauchly) (_John William Mauchly_) un [Dž. Ekerta](https://en.wikipedia.org/wiki/J._Presper_Eckert) (_J. Presper Eckert_) vadībā. 1946. gada februārī ENIAC tika atslepenots un tā paša gada vasarā šajā skolā profesors Mouklijs sāka pasniegt [lekciju kursu](http://curation.cs.manchester.ac.uk/computer50/www.computer50.org/mark1/moore.school/list.html) par datoriem, kas vēsturiski bija pirmās lekcijas par datoriem pieejamas plašai auditorijai. Mūsdienās šīs lekcijas izmanto kā atsauci binārmeklēšanas algoritma aizsākumam (22. lekcija - “_Sorting and collating_”).

Jāpiebilst, ka binārmeklēšanas algoritma pamatā ir [bisekcijas tehnika](https://en.wikipedia.org/wiki/Bisection_method), kuru dažādi matemātiķi izmantoja krietni senāk. Piemēram, neatkarīgi viens no otra, 1817. gadā [Bolcāno](https://en.wikipedia.org/wiki/Bolzano) un 1821. gadā [Košī](https://en.wikipedia.org/wiki/Augustin-Louis_Cauchy), izmantoja bisekcijas tehniku, lai pierādītu [teorēmu par starpvērtībām](https://en.wikipedia.org/wiki/Intermediate_value_theorem), kuru vēlāk nosauca abu zinātnieku vārdā - par Bolcāno-Košī teorēmu. Kamēr šie abi pēdējie bisekcijas tehniku pielietoja nepārtrauktu funkciju vispārīgiem gadījumiem, jau 1795. gadā [Lagranžs](https://en.wikipedia.org/wiki/Joseph-Louis_Lagrange) bisekcijas tehniku izmantoja, lai risinātu konkrētu problēmu - atrastu aproksimētu (tuvināti izteiktu) polinoma sakni. Līdzīgu tehniku (piezīme, šķelšanu 10 daļās) izmantoja [Simons Stevins](https://en.wikipedia.org/wiki/Simon_Stevin) (16. gs.) - lai atrastu kubiska polinoma sakni (_[Stevin’s cubic and the IVT](https://arxiv.org/pdf/1202.4153.pdf)_). Atgriežoties pie Mouklija, tad viņš bija pirmais, kurš bisekcijas metodi pielietoja informācijas meklēšanā.

#### Binārmeklēšanas piemērs

Mario priekšā atrodas 16 kastes un katrā no tām ir noslēpts skaitlis.


Mario nezin nevienu skatili un pat skaitļu diapozonu, bet viņš zin, ka kastes ir novietotas secībā atbilstoši sakārtotai skaitļu rindai sākot ar māzāko un beidzot ar lielāko skaitli. Mario var uzlekt uz jebkuras kastes un pārbaudīt, kāds skaitlis tur ir noslēpts. Turklāt, pieņemsim, ka nav starpības, vai lēciens būs uz otrās vai uz pēdējās kastes - tas cik daudz enerģijas patērēs Mario, nav atkarīgs no lēciena garuma - jebkruš lēciens patērē vienādu enerģijas daudzumu.

**Uzdevums:**

* noskaidrot vai starp 15 kastēm atrodas vismaz viena tāda kaste, kurā ir apslēpts skaitlis 77;
* izdomāt stratēģiju, lai lēcienu skaits būtu pēc iespējas mazāks.


Kā redzams attēlā, tad Mario skaitli 77 atrada, izdarot tikai 3 lēcienus. Mario stratēģija bija sadalīt apskatāmo apgabalu divās daļās, sākumā atklājot apslēpto skaitli, kurš ir pa vidu. Ja nepaveicās - atklātais skaitlis nav tas, kurš tiek meklēts, tad jāveic nākamais lēciens. Tā kā tā ir sakārtota skaitļu virkne, tad loģiski, ka meklējamais skaitlis atrodas vai nu pa labi, vai pa kreisi no pirmā atklātā skaitļa. Ja tas atrodas pa labi, tad atmetam kreiso pusi un turpinām meklēt skaitli labajā pusē, atkal sadalot uz pusēm. Procedūru atkārtojam tik ilgi, kamēr tiek atrasts meklējamais skaitlis.

Binārmeklēšana ir klasisks samazini un valdi algoritmu paradigmas piemērs, kurā samazināšana notiek pēc nemainīga koeficienta 1/2. Tāds algoritms nodrošina to, ka meklējamā vērtība tiks atrasta logaritmiskā laikā jeb ar Binārmeklēšana ir klasisks samazini un valdi algoritmu paradigmas piemērs, kurā samazināšana notiek pēc nemainīga koeficienta 1/2. Tāds algoritms nodrošina to, ka meklējamā vērtība tiks atrasta logaritmiskā laikā jeb ar log2 n iterācijām, kur iterācijām, kur n ir virknes garums. Piemēram, ja kāds skaitlis jāatrod starp 16 skaitļiem, tad pietiek 4 iterācijas, bet ja starp 32 skaitļiem, tad pietiek ar 5 iterācijām.


Kad amerikāņu datorzinātnieks [Džons Bentlijs](https://en.wikipedia.org/wiki/Jon_Bentley_(computer_scientist)) profesionālu programmētāju kursos uzdeva uzrakstīt programmu binārās meklēšanas algoritmam, viņš atklāja, ka pēc vairāku stundu darba 90% no risinājumiem nebija korekti, lielākoties tāpēc, ka [galējos gadījumos](https://en.wikipedia.org/wiki/Edge_case) (*edge case*) algoritma implementācija nesrādāja vai atgrieza nepareizu atbildi. 1988. gadā publicētais [pētījums](https://www.uni-weimar.de/fileadmin/user/fak/medien/professuren/Mediensicherheit/Teaching/SS15/SSS/p190-pattis.pdf) liecina, ka precīzs binārās meklēšanas kods ir atrodams tikai piecās no divdesmit mācību grāmatām. Turklāt 1986. gadā paša Bentlija publicētais kods grāmatā “[Programming Pearls](https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/pearls-2.pdf)” ietvēra [pārpildes kļūdu](https://en.wikipedia.org/wiki/Integer_overflow), kas vairāk nekā divdesmit gadus netika atklāta. Programmēšanas valodā Java binārās meklēšanas implementācija vairāk nekā deviņus gadus bija ar to pašu pārpildes kļūdu.

Populārākais binārās meklēšanas algoritma pielietojums ir atrodams binārmeklēšanas koka un B-koka datu struktūrās.

## Koks (*tree*)

Jēdziena “koks” aizsākumi meklējami [diskrētās matemātikas](https://en.wikipedia.org/wiki/Discrete_mathematics) apakšnozarē [grafu teorijā](https://en.wikipedia.org/wiki/Graph_theory), jo mūsdienās [koks](https://en.wikipedia.org/wiki/Tree_(graph_theory)) tiek uzskatīts par saistītu, neorientētu un aciklisku [grafu](hhttps://en.wikipedia.org/wiki/Graph_(discrete_mathematics)).

<span></span>17. gs. matemātiķis un filozofs [Gotfrīds Vilhelms Leibnics](https://en.wikipedia.org/wiki/Gottfried_Wilhelm_Leibniz) apsvēra tādu domu, ka bez [matemātiskās analīzes](https://en.wikipedia.org/wiki/Calculus) un [analītiskās ģeometrijas](https://en.wikipedia.org/wiki/Analytic_geometry) vajadzētu vēl būt “pozīcijas analīzei”, kura attiektos tikai uz pozīciju (ignorējot lielumus), tāpēc Leibnics 1670. gadā vēstulē [Kristiānam Heigensam](https://en.wikipedia.org/wiki/Christiaan_Huygens) rakstīja:

> Es neesmu apmierināts ar algebru [..], es uzskatu, ka mums ir vajadzīgs vēl viens ģeometriskas vai lineāras analīzes veids, kas tieši attiecas uz pozīciju, tāpat kā algebra attiecas uz lielumiem.

Vairāk kā pusgadsimtu vēlāk Leibnica ierosinājums īstenojās praktiskā uzdevumā. 18. gs. dominējošākais matemātiķis [Leonards Eilers](https://en.wikipedia.org/wiki/Leonhard_Euler) 1736. gadā formulēja matemātiski pirmo grafu teorijas uzdevumu (par [Kēnigsbergas tiltiem](https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg)). Uzdevuma būtība bija sekojoša. Kēnigsbergas pilsētā (mūsdienu Kaļiņingradā) bija 7 tilti un vajadzēja atrast tādu ceļu, kurš ved pāri visiem tiltiem, bet katru tiltu drīkst sķērsot tikai vienu reizi, turklāt, ceļu beidzot, jāatgriežas tajā pašā punktā, no kura ceļš sākts. Eilers ieviesa un definēja jēdzienu “[Eilera cikls](https://en.wikipedia.org/wiki/Eulerian_path)” un ar to pierādija, ka uzdevumam nav atrisinājuma. Eilera darbu var uzskatīt par grafu teorijas pirmssākumu, turklāt Eilera darbu turpināja pētīt un apkopoja [Košī](https://en.wikipedia.org/wiki/Augustin-Louis_Cauchy) un [Liljē](https://en.wikipedia.org/wiki/Simon_Antoine_Jean_L%27Huilier), liekot pamatus matemātikas apakšnozarei - [topoloģijai](https://en.wikipedia.org/wiki/Topology).

*Kēnigsberga XVII—XVIII gadsimtā (1652. gada karte)*

Vairāk kā vienu gadsimtu vēlāk pēc Eilera darba par Kēnigsbergas tiltiem, kamēr [Johans Benedikts Listings](https://en.wikipedia.org/wiki/Johann_Benedict_Listing) ieviesa topoloģijas jēdzienu, 1857. gadā matemātiķis, Kembridžas universitātes profesors [Arturs Keilijs](https://en.wikipedia.org/wiki/Arthur_Cayley) publicēja [dokumentu](https://www.jstor.org/stable/pdf/2369158.pdf) ar nosaukumu “*On the theory of the analytical forms called trees*”, kurā lietoja jēdzienu “koks”. Keilijs, nedefinēja terminu “koks”, bet identificēja noteiktu struktūru, kuru sauca par koku. Keilijs šo struktūru saistīja ar vielu ķīmisko sastāvu. Sākās matemātikas un ķīmijas ideju saplūšana, kas kļuva par daļu no grafu teorijas standarta terminoloģijas. Izmantojot grafu teorijas pamatus, datorzinātnē tika radītas jaunas abstraktas datu struktūras.

## Binārais koks (*binary tree*)

Datorzinātnē [binārais koks](https://en.wikipedia.org/wiki/Binary_tree) ir hierarhiska [kokveida datu struktūra](https://en.wikipedia.org/wiki/Tree_(data_structure)). No grafu teorijas perspektīvas binārais koks pieder pie [n-koku](https://en.wikipedia.org/wiki/M-ary_tree) (*m-ary tree*) klases. N-koks ir sakņots koks (jeb [sakņots grafs](https://en.wikipedia.org/wiki/Rooted_graph)), kur katram mezglam ir ne vairāk kā N bērnu. Binārais koks ir īpašs gadījums, kur N = 2. Cits īpašs gadījums, piemēram, ir [ternārais koks](https://en.wikipedia.org/wiki/Ternary_tree), kur N = 3. Jāatzīmē, ka par sakņotu koku (*rooted tree*) sauc tādu grafu, kuram viena virsotne ir īpaši izdalīta, un to sauc par koka sakni (*root*). Attēlā var redzēt erminoloģiju, ko izmanto, lai raksturotu bināro koku.


## Binārais meklēšanas koks (*binary search tree*)

[Binārais meklēšanas koks](https://en.wikipedia.org/wiki/Binary_search_tree) (BMK) ir binārā koka (BK) variants. Atšķirībā no BK, kur mezgli vienkārši attēlo hierarhiskus datus, tad BMK mezgli ir sakārtoti tā, lai meklēšanu pa koku varētu veikt, izmantojot binārās meklēšanas principu. BMK atslēgas ir organizētas tā, ka kreisā bērna atslēga ir mazāka vai vienāda par paša mezgla atslēgu, bet labā – lielāka vai vienāda. Šķērsojot koku no saknes līdz nākamajam mezglam, tiek salīdzināta meklējamā vērtība ar mezgla vērtību, un pamatojoties uz salīdzinājuma rezultātu, meklēšana tiek turpināta vai nu pa labi, vai nu pa kreisi.

Piemēram, lai atrastu skaitli 4 skaitļu virknē [1, 3, 4, 6 ,7, 8, 10, 13, 14], binārais meklēšanas koks un salīdzināšanas operācijas izskatīsies sekojoši:


Dotajā piemērā BMK ir balansēts koks, kas nozīmē, ka jebkura mezgla labā un kreisā apakškoka dziļumu starpības modulis nav lielāks par 1.


*Binārie meklēšanas koki (balansēts / nebalansēts)*

Svarīgi, lai BMK ir balansēts, jo, piemēram, koks, kurā visi mezgli ir vērsti tikai uz vienu pusi (*skewed tree*) izskatīsies nevis pēc koka, bet pēc līnijas. Tādā gadījumā kokam zūd jēga un, informācijas meklēšanas ziņā tam vairs nav nekādu priekšrocību salīdzinājumā ar [sarakstu](https://en.wikipedia.org/wiki/List_(abstract_data_type)). Koka balansēšana nodrošina labāku meklēšanas laiku - O(log (n)), nevis O(n).

**Kā izveidot balansētu bināro meklēšanas koku?**

Piemēram, ir dota nesakārtota skaitļu virkne [4, 8, 10, 14, 1, 7, 13, 3, 6]. No šīs skaitļu virknes ir jāizveido binārais meklēšanas koks, turklāt tam jābūt balansētam. To var izdarīt divos soļos, izmantojot topika sākumā minēto skaldi un valdi principu:

* Pirmais solis. Skaitļu virkne ir jāsakārto augošā secībā. To var izdarīt izmantojot *merge sort* algoritmu, kurš tika iztirzāts topika sākumā.
* Otrais solis. Izmantojot skaldi un valdi principu katrā iterācijā jāizdala skaitlis, kurš skaitļu virknē atrodas pa vidu. Tas jādara tiklīdz katrs skaitlis kļūst par koka mezglu.


**Kā pievienot jaunu mezglu binārājā meklēšanas kokā?**

Jauna atslēga binārajā meklēšanas kokā vienmēr tiek ievietota kā lapa. Izmantojot binārās meklēšanas principu, sākot no koka saknes jāvirzās pa koku tiklīdz tiek sasniegta kāda no lapām un tās kreisajā vai labajā pusē jāpievieno jauna atslēga.

**Kā izdzēst?**

Ir vairāki veidi kā izdzēst mezglu no binārā meklēšanas koka. 1962. gadā, amerikāņu matemātiķis un datozinātnieks, [Tomass Hibards](https://en.wikipedia.org/wiki/Thomas_N._Hibbard) piedāvāja savu [algoritmu](http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/BST-delete.html), un mūsdienās tas ir labākais zināmais dzēšanas algoritms.

**Re-balansēšana**

Jaunu mezglu ievietošana vai dzēšana var izjaukt koka balansu (padarīt koku šķību), tāpēc pēc katras šādas operācijas koku nepieciešams re-balansēt. [Pašbalansējoši binārās meklēšanas koki](https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree) (*self-balancing binary search tree*) atrisina šo problēmu, izdarot kokā transformācijas, piemēram, [koka pagriešanu](https://en.wikipedia.org/wiki/Tree_rotation). Lai arī tas prasa papildus skaitļošanas resursus, tomēr tas atmaksājas vēlāk, jo šāda pieeja uztur optimālu koka struktūru, lai nodrošinātu ātru meklēšanas operāciju izpildi. Tomēr datorzinātnē koka re-balansēšanai transformācijas nenotiek katrā jauna mezgla pievienošanas vai dzēšanas laikā, jo tas prasītu daudz skaitļojamos resursus, tāpēc praksē pastāvīgi uzturēt ideāli balansētu koku nav optimāli un ir pieļaujams, ka koks ir mazliet šķībs. Jāatzīmē, ka koka šķībums ir atsevišķs temats, kuru apskata [nejaušu bināro koku](https://en.wikipedia.org/wiki/Random_binary_tree) varbūtības analīzē un ir izgudrotas tādas datu sruktūras (piem., [skew heap](https://en.wikipedia.org/wiki/Skew_heap), [treap](https://en.wikipedia.org/wiki/Treap)), kurās koka šķībums tiek izmantots kā priekšrocība.

## AVL koks (*AVL Tree*)

<span></span>1962. gadā tika publicēts [dokuments](http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26964&option_lang=rus) (*доклад*) ar nosaukumu “*ОДИН АЛГОРИТМ ОРГАНИЗАЦИИ ИНФОРМАЦИИ*”, kurā divi PSRS zinātnieki aprakstīja savu izgudrojumu, nosauktu par [AVL koku](https://en.wikipedia.org/wiki/AVL_tree). Tā ir pirmā izgudrotā datu struktūra, kura pieder pie pašbalansējošu binārmeklēšanas koku klases. [Dokuments angļu valodā](https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf).

AVL koka konstrukcija nodrošina koka līdzsvaru pēc katras ievietošanas operācijas, tāpēc AVL koks ir vairāk efektīvs, ja lielākoties ir meklēšanas operācijas, nekā ievietošanas operācijas. AVL koks tika ieviests uz operatīvās atmiņas balstītiem risinājumiem, tāpēc šāds koks nav paredzēts lielu datu kolekciju glabāšanai. Kad datu kolekcija ir tik liela, ka tā neietilpst operatīvajā atmiņā, tad risinājums ir B-Koks.

## B-Koks (*B-Tree*)

<span></span>1970. gadā tika publicēts [dokuments](https://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf) ar nosaukumu “*Organization and maintenance of large ordered indices*”, kurā divi amerikāņu zinātnieki aprakstīja savu izgudrojumu, sauktu par B-Koku (*B-Tree*). Viena no bieži dzirdētām kļūdām ir tā, ka B-Koks tiek saukts par bināro koku (*binary tree*), bet tas nav viens un tas pats. Burts “B” nenozīmē “binārais” un patiesībā paši autori nesniedz konkrētu skaidrojumu burtam “B”. Kā atzīst pats autors [šajā video](https://vimeo.com/73481096) (16 min 5 sec), tad tas var nozīmēt daudzko.

> You just have no idea what a lunchtime conversation can turn into. So there we were, [indistinct] and I, at lunch , we had to give the thing a name. And we were, so, B, we were thinking… B is, you know… We were working for Boeing at the time, we couldn't use the name without talking to the lawyers. So, there is a B. It has to do with balance, another B. Bayer was the senior author, who did have several years older than I am and had many more publications than I did. So there is another B. And so, at the lunch table we never did resolve whether there was one of those that made more sense than the rest. What really lies to say is: the more you think about what the B in B-trees means, the better you understand B-trees.

***Turpinājums sekos...***