Dvejetainis medis yra subalansuotas, jei medžio aukštis yra O(Log n), kur n yra mazgų skaičius. Pavyzdžiui, AVL medis išlaiko O(Log n) aukštį, įsitikindamas, kad skirtumas tarp kairiojo ir dešiniojo pomedžio aukščių yra ne didesnis kaip 1. Raudonai juodi medžiai išlaiko O(Log n) aukštį, įsitikindami, kad skaičius juodųjų mazgų kiekviename kelyje nuo šaknies iki lapo yra vienodi ir kad nėra gretimų raudonų mazgų. Subalansuotos dvejetainės paieškos medžiai yra naudingi našumui, nes suteikia O (log n) laiką paieškai, įterpimui ir ištrynimui.
Subalansuotas dvejetainis medis yra dvejetainis medis, atitinkantis 3 sąlygas:
- Bet kurio mazgo kairiojo ir dešiniojo medžio aukštis nesiskiria daugiau nei 1.
- To mazgo kairysis pomedis taip pat subalansuotas.
- Dešinysis to mazgo pomedis taip pat subalansuotas.
Vienas mazgas visada yra subalansuotas. Jis taip pat vadinamas dvejetainiu medžiu su subalansuotu aukščiu.
Pavyzdys :
Subalansuotas ir nesubalansuotas dvejetainis medis
Tai dvejetainio medžio tipas, kuriame kiekvieno mazgo kairiojo ir dešiniojo pomedžio aukščio skirtumas yra 0 arba 1. Aukščiau pateiktame paveikslėlyje šakninis mazgas, kurio reikšmė 0, yra nesubalansuotas, jo gylis yra 2 vienetai. .
Subalansuoto dvejetainio medžio taikymas:
- AVL medžiai
- Raudonas Juodas Medis
- Subalansuotas dvejetainis paieškos medis
Subalansuoto dvejetainio medžio pranašumai:
- Neardomuosius atnaujinimus palaiko subalansuotas dvejetainis medis, turintis tokį patį asimptotinį efektyvumą.
- Diapazono užklausos ir iteracija teisinga seka yra įmanomos dėl subalansuoto dvejetainio medžio.