Subalansuotas dvejetainis medis taip pat žinomas kaip subalansuoto aukščio medis. Jis apibrėžiamas kaip dvejetainis medis, kai skirtumas tarp kairiojo ir dešiniojo pomedžio aukščio yra ne didesnis kaip m, kur m paprastai yra lygus 1. Medžio aukštis yra briaunų skaičius ilgiausiame kelyje tarp šaknies mazgas ir lapo mazgas.
Aukščiau pateiktas medis yra a dvejetainis paieškos medis . Dvejetainis paieškos medis yra medis, kuriame kiekvienas mazgas kairėje turi mažesnę reikšmę nei jo pirminis mazgas, o mazgas dešinėje turi didesnę reikšmę nei jo pirminis mazgas. Aukščiau pateiktame medyje n1 yra šaknies mazgas, o n4, n6, n7 yra lapų mazgai. n7 mazgas yra toliausiai nuo šakninio mazgo. n4 ir n6 turi 2 briaunas, o tarp šakninio mazgo ir n7 mazgo yra trys kraštai. Kadangi n7 yra toliausiai nuo šakninio mazgo; todėl aukščiau esančio medžio aukštis yra 3.
Dabar pamatysime, ar aukščiau esantis medis yra subalansuotas, ar ne. Kairiajame pomedyje yra mazgai n2, n4, n5 ir n7, o dešiniajame pomedyje yra mazgai n3 ir n6. Kairysis pomedis turi du lapų mazgus, ty n4 ir n7. Tarp mazgų n2 ir n4 yra tik viena briauna ir dvi briaunos tarp mazgų n7 ir n2; todėl mazgas n7 yra toliausiai nuo šakninio mazgo. Kairiojo pomedžio aukštis yra 2. Dešinysis pomedis turi tik vieną lapo mazgą, t.y., n6, ir turi tik vieną kraštą; todėl dešiniojo pomedžio aukštis yra 1. Skirtumas tarp kairiojo pomedžio ir dešiniojo pomedžio aukščių yra 1. Kadangi gavome reikšmę 1, galime teigti, kad aukščiau pateiktas medis yra aukščio subalansuotas medis. Šis aukščių skirtumo apskaičiavimo procesas turėtų būti atliekamas kiekvienam mazgui, pvz., n2, n3, n4, n5, n6 ir n7. Kai apdorosime kiekvieną mazgą, pamatysime, kad k reikšmė yra ne didesnė kaip 1, todėl galime sakyti, kad aukščiau pateiktas medis yra subalansuotas dvejetainis medis .
Aukščiau pateiktame medyje n6, n4 ir n3 yra lapų mazgai, kur n6 yra toliausiai nuo šaknies mazgo esantis mazgas. Tarp šaknies mazgo ir lapo mazgo yra trys kraštai; todėl aukščiau pateikto medžio aukštis yra 3. Kai šakniniu mazgu laikome n1, tai kairiajame pomedyje yra mazgai n2, n4, n5 ir n6, o pomedyje yra mazgas n3. Kairiajame pomedyje n2 yra šaknies mazgas, o n4 ir n6 yra lapų mazgai. Tarp n4 ir n6 mazgų n6 yra toliausiai nuo šakninio mazgo, o n6 turi dvi briaunas; todėl kairiojo pomedžio aukštis yra 2. Dešiniajame pomedžio kairėje ir dešinėje yra vaikas; todėl dešiniojo pomedžio aukštis yra 0. Kadangi kairiojo pomedžio aukštis yra 2, o dešiniojo pomedžio aukštis yra 0, tai skirtumas tarp kairiojo ir dešiniojo pomedžio aukščio yra 2. Pagal apibrėžimą skirtumas tarp kairiojo pomedžio ir dešiniojo pomedžio aukščio neturi būti didesnis nei 1. Šiuo atveju skirtumas yra 2, kuris yra didesnis nei 1; todėl aukščiau pateiktas dvejetainis medis yra nesubalansuotas dvejetainis paieškos medis.
java masyvai
Kodėl mums reikia subalansuoto dvejetainio medžio?
Supraskime subalansuoto dvejetainio medžio poreikį per pavyzdį.
Aukščiau pateiktas medis yra dvejetainis paieškos medis, nes visi kairiojo pomedžio mazgai yra mažesni už pirminį mazgą, o visi dešinieji pomedžio mazgai yra didesni už pirminį mazgą. Tarkime, kad norime aukščiau esančiame medyje rasti reikšmę 79. Pirma, lyginame mazgo n1 reikšmę su 79; kadangi 79 reikšmė nėra lygi 35, o ji yra didesnė už 35, tai pereiname prie mazgo n3, t.y., 48. Kadangi reikšmė 79 nėra lygi 48, o 79 yra didesnė nei 48, tai judame į dešinę 48 antrinis. 48 mazgo dešiniojo antrinio elemento reikšmė yra 79, kuri yra lygi reikšmei, kurią reikia ieškoti. Elemento 79 paieškai reikalingas apynių skaičius yra 2, o didžiausias bet kurio elemento paieškai reikalingas apynių skaičius yra 2. Vidutinis elemento paieškos atvejis yra O(logn).
Aukščiau pateiktas medis taip pat yra dvejetainis paieškos medis, nes visi kairiojo pomedžio mazgai yra mažesni už pagrindinį mazgą, o visi dešinieji pomedžio mazgai yra didesni už pirminį mazgą. Tarkime, kad aukščiau esančiame medyje norime rasti reikšmę 79. Pirmiausia lyginame reikšmę 79 su mazgu n4, ty 13. Kadangi reikšmė 79 yra didesnė nei 13, pereiname prie 13 mazgo dešiniojo antrinio, ty n2 (21). Mazgo n2 reikšmė yra 21, kuri yra mažesnė nei 79, todėl vėl pereiname į 21 mazgo dešinę. 21 mazgo dešiniojo antrininko reikšmė yra 29. Kadangi reikšmė 79 yra didesnė nei 29, tai mes judame į dešinę 29 mazgo vaikas. 29 mazgo dešiniojo vaiko reikšmė yra 35, kuri yra mažesnė nei 79, todėl pereiname prie 35 mazgo dešiniojo antrinio, t. 48 mazgo dešiniojo antrinio mazgo reikšmė yra 79, kuri yra lygi reikšmei, kurią reikia ieškoti. Šiuo atveju elemento paieškai reikalingas apynių skaičius yra 5. Šiuo atveju blogiausias atvejis yra O(n).
Jei mazgų skaičius didėja, medžio diagramoje1 naudojama formulė yra efektyvesnė už formulę, naudojamą medžio diagramoje2. Tarkime, kad abiejuose aukščiau esančiuose medžiuose galimų mazgų skaičius yra 100 000. Norint ieškoti bet kurio elemento medžio diagramoje2, laikas yra 100 000 µs, o laikas, kurio reikia elemento paieškai medžio diagramoje, yra log(100 000), kuris yra lygus 16,6 µs. Galime stebėti didžiulį laiko skirtumą tarp dviejų aukščiau esančių medžių. Todėl darome išvadą, kad balanso dvejetainis medis leidžia ieškoti greičiau nei linijinio medžio duomenų struktūra.