4 страница. 1. Осы түрлендіру нәтижесінде алынған бинарлы ағаш іздеудің бинарлы ағашы болуы керек;

1. Осы түрлендіру нәтижесінде алынған бинарлы ағаш іздеудің бинарлы ағашы болуы керек;

2. Нәтижелік ағаш AVL ағашы болуы керек;

3. Түрлендіру жеткілікті түрде тиімді болуы керек.

Осыған байланысты, жаңа төбе қосқанға дейін AVL ағашы болған, бірақ балансы жаңа төбе қосу нәтижесінде бұзылған ағаштың ішкі ағаштарымен орындалатын екі операцияны қарастырайық. Қажет болған жағдайда бұл операциялар кез-келген бинарлы іздеу ағашымен жүргізіле алады.

Алғашқы операция сол жақ бұрылыс, мағынасын келесі сурет ұғындырады.

Сол жақ бұрылыс

Сонымен бинарлы іздеу ағашымен сол жақ немесе оң жақ бұрылыс операциясын орындау нәтижесінде алынған ағаш бинарлы іздеу ағашы болып қалады. Ескерте кетсек, сол жақ немесе оң жақ бұрылыс операциясын орындау онша қиын шаруа емес, себебі олардың әрбірін орындағанда тек үш сілтемені ғана баптау керек және ең маңыздысы бұл , , ішкі ағаштарынан тәуелсіз жүргізіледі.

29. Стек және оның қолданылуы

Стек – деректер құрылымы, кейбір жағдайларда магазин, динамикалық жады деп аталады. Осындай стек алдын-ала тізбектеліп орналасқан шексіз «көршілес ұяшықтардан» тұрады, олардың ішінен «стек басы» және «түбі» ерекше ажыратылады. Процесстің кез-келген уақыт мезетінде тек стек басына ғана оқу немесе жазу мүмкіндігі болады. Осыған орай процесс барысында стек не өсіп немесе кеміп отырады. Стек реттелген ұяшықтардан құрылған жады. Осы жадты тізбек сурет 3.1. немесе тізім ретінде сурет 3.2. көрсетілгендей ұйымдастыруға болады.

Сурет 3.1 Сурет 3.2

Егер стек тізім ретінде ұйымдастырылса да, оны тізбектелген тізім ретінде көрсету жеңіл болып келеді. Ары қарай екі мысал қарастырайық. Мысалдарда стек арқылы арифметикалық өрнектерді есептеуді ұйымдастрады. Бірінші өрнек (a + b * c) / d болсын, оның ағашы келесі түрде болады.

Сурет 3.3

Постфикстік жазбасы a b c * + d / болады. онда берілген өрнекті есептеу үшін процесстің әр мезетіндегі стек тізбегі келесі суретте көрсетілгендей болады.

Келесі мысал жоғарыда қарастырылған (a + b) * c-d / f өрнекті береді. Есептеу мезетінде айнымалылардың мәндері белгілі болсын a=3, b= -1, c=2, d=6, f=3. Онда

Постфикстік жазбаны қолдану кезінде операция символы тікелей өзінің операндтары артынан жүріп отырады, және де есептеу мезетінде, операндтардың мәндері белгілі болып отырады.

Стекке қолданатын қарапайым операциялар. Мұндай операциялар (командалар) саны көп емес, бірақ олар жеткілікті көптүрлі және келесі операциялардан тұрады:

push – стекке енгізіледі. Дәл айтқанда стек басына орнатылады.

pop – стек басынан сөз алынып, белгілі бір айнымалы мәніне тағайындалады.

Стектің басындағы екі ұяшыққа қолданатын арифметикалық және логикалық операциялар да бар, олар нәтижелерді де стекке жазады.

Осыған қоса процедуралардың локальді айнымалыларымен және процедуралардың өзімен жұмыс жасау командалары, константалармен жұмыс жасау командалары және шартты немесе шартсыз алмасу командалары және шартты немесе шартсыз алмасу командалары, т.б. командалар.

30. Айырбастаумен сұрыптайтын алгоритмдер

Бұл сұрыптау алгоритмдерінің класының өкілдері ретінде көпіршікпен сұрыптау, сонымен қатар шеллдың сұрыптау алгоритмі, тез реттеу алгоритмі, т.б. алгоритмдер мысал бола алады. Шеллдің сұрыптау алгоитмін қарастырайық. Шеллдің реттеу алгоритмі көпіршіктік сұрыптау алгоритмін жалпылайды. Салыстырылатын бастапқы массивтің екі жақын орналасқан элементтерін ғана емес, бекітілген d қашықтықта орналасқан элементтерді де салыстырады. Бірінші қадамда массивтің жарты ұзындығына орналасқан элементтерді салыстырады, яғни d=n\2 тең. Келесі қадамда d:=n\2 деп есептеледі, ары қарай d=1 қашықтықтағы элементтер салыстырылып қажет жерде алмастырылып отырады. Осы процедураның соңғы кезеңдерінде элементтер арасында қашықтық d=1 болған кезде алмастыру қажет етпеуі мүмкін, мұның себебі алғашқы кезеңдерде салыстырылып және

алмастырылған элементтер өз орындарында орналасқанынан болады. Яғни кезеңдердің айналуына байланысты алмастыру саны төмендей береді. Шеллдің реттеу алгоритмінің мысалы:

25, 31, 7, 4, 10, 18, 5, 13, 21, 11, 9, d=5

18, 5, 7, 4, 10, 9, 31, 13, 21, 11, 25, d=3

4, 5, 7, 18, 10, 9, 11, 13, 21, 31, 25, d=1

4, 5, 7, 10, 9, 11, 13, 18, 21, 25, 31

4, 5, 7, 9, 10, 18, 13, 21, 31, 11, 25

Ескерту: Берілген алгоритмді қолмен трассировкасын жүргізгенде әр алмастырудан кейін массивті жаңа жолға көшіру жақсылау болады. Осылай алгоритм соңғы мысалға қарағанда кішкентай қадамдармен орындалады. Қарастырылып отырған мысалымыз үшін алгоритмнің алғашқы қадамдары келесі түрде болады. Суретте бағыттауыш доғалар алмастыруды көрсеттеді:

25, 31, 7, 4, 10, 18, 5, 13, 21, 11, 9, d=5

18, 31, 7, 4, 10, 25, 5, 13, 21, 11, 9

...

18, 5, 7, 4, 10, 9, 31, 13, 21, 11, 25

18, 5, 7, 4, 10, 9, 31, 13, 21, 11, 25, d=3

4, 5, 7, 18, 10, 9, 31, 13, 21, 11, 25

...

bubble sort

4, 5, 7, 9, 10, 11, 13, 18, 21, 25, 31

31. Сызықтық хештеу

Элементті кірістірген кезде кестені жол бойынша қатарлап көру жинақталып қалуға әкеліп соқтырады,т.с.элемент мәліметтерінің жинақталуы уақыт өте келе ұзын кластерлердің жиналуына әкеледі.Кластер үлкен болған сайын ол уақыт өте келе одан да үлкен болуы мүмкін.Мұндай бұрыс эффект кірістіруі бар сызықтық хештеу процедурасына тән және бұл кестені практика жүзінде қолдануды шектейді.

Сызықтық шектеу жағдайында барлығы онша күрделі болып көрінбейді. Мұнда бұрынғыдай m хеш кестенің ұзындығы болсын, онда хеш функция ретінде мынадай функцияны алуға болады.

h(p)=pmod m;

мұнда p белгінің мәні a mod операцияның белгіленуі бүтін p санын m бүтін оң санына бөлгендегі қалдықты қайтаратын операция.

Егер белгінің кез келген екі p’ p” мәндері үшін p’≠p” болғанда h(p’)≠h(p”) болса онда барлығы жақсы.Белгіленгендей бұл жағдайда біз мінсіз немесе идеалды хеш функциямен жұмыс істейміз, шекті өлшемді жағдайда екі p,h(p) бағанды кесте түрінде берсек те болар еді.Егер әрине белгілер мәндері натуралды қатардың бөлігін құрамайтын болса мысалы,[1,2,…,n] (3.1a сурет) онда мүмкін көп жағдайда бұл кестеде “ақ дақтар” табылады(3.1в сурет).Соңғы ретте кестеде бар белгіге сәйкес элементті тезірек іздеуді мүмкін етуге болады.

Қарапайым нұсқада белгілі бір массив үшін жолында екінші бағандағы мәні тең болуы мүмкін. Егер де кестенің өзі кестесімен салымтырғанда жинақы түрде жазылса, ал оның бірінші бағаны реттелген болса, онда бүкіл кестені тегіс іздегенге қарағанда осы кесте бойынша іздеу реттелген массивте іздеудегідей болуына басымдық беріледі. Сонымен жай кесте салыстырмалы жалпы жағдайдың өзінде бізге берілген есептің эффективті шешімін табуда кейбір арнайы жағдай/дан басқа жағдайларда бөгет болады. Әрине хеш кестеде де бос жол/ болуы тиіс бірақ олар көп мөлшерде болмауы к/к, тек коллизияны шешуге керекті мөлшері ғана к/к болады.

Нақты жағдайда әр түрлі p’ p”(p’≠p’’) мәндері үшін h(p’)=h(p”) орын алатын жағдайлар туып отырады.Егер де бұл ретте h(p’) нөмірлі кесте жол ұяшығы p’ мәнін алған болса,онда p” мәнін орналастыратын бос ұяшықтарды айқындайтын хеш кесте жолдарын тексеретін процедура ұйымдастыру керек.

Сызықтық хеширлеу жағдайында мынандай хеш функция түрін қолдану ұсынылады:

(*) h(p,i)=(h(p)+i)mod m, h(p,0)=h(p)mod m;

Iиндексі бұл тексеру нөмірі i:=0,1,…,m-1.

Сызықтық хештеу схемасын жеңіл жасауға болады,алайда жоғарыда айтылып кеткендей оны қолдану жинақталып қалуға әкеліп соқтырады, мәліметтердің жинақталуы өсіп келе жатқан кластерлерге айналады.

32. Квадраттық xештеу және оның ерекшеліктері

Мұнда f(i) функциясын қолайлы таңдау арқылы сызықтық хештеуде алғашқы кластерлер пайда болу мәселесін болдырмауға болады. Айқын түрде f(i) функциясымен байланысы жоқ квадрат ортасы әдісінен бастап, мұнда бірнеше кең таралған әдістер бар. Бұл әдістерде кілт өз-өзіне көбейтіледі және хеш-кестеде жазылған хеш-функцияның мәні ретінде хеш-кестеге жазылатын кебейтінділердің орта цифрларының белгңлң саны таңдалады.

Квадратгық хештеудің басқа жүзеге асыруларында f(i) функциясы айқын беріледі.

a) f(i)=i², бұл мынаны береді

h (р, i) = (h (р) + i²) mod m, i =0,1,...,m-1

b) f(i)=± i², келесі арқылы белгілейміз

h (p, i) = (h (p) + i²)mod m, i = 0,l,...,m-l

с₁ жэне с₂ коэффициенттері р-дан тәуелсіз деген шартпен келесі схеманы да қарастыруга болады

c) f(i)= с₁ × i + с₂ × i², с₂ ≠ 0,

h (р, i) = (h (р) + с₁ × i + с₂ × i²) mod m, i = 0,l,...,m-l,

Бұған өте ұқсас, әpi қызықты, бipaқ с) схемасының жеке жағдайы емес квадраттық коэффициенттер әдісі де бар:

cl) h (p, i) = (h(p)+ i +q × i₂)mod m,

мұндағы q бұл р-ны m-ға бөлгендегі бөлінді.

Әpбip с) - a) бipeyiнің таңдалуы m санын ұқыпты таңдауды қажет етеді, одан басқа, m жай сан немесе екінің дәрежесі болумен қатар берілген есептің анықталу сипаттамасының қосымша талабы болуы мумкін.

Сонымен қатар, бұның басқа да ерекшелік/і де бар, м/ы таңдау

a)Kipicтipy есебінің шешілуінің қолма-қол дәлелдеме/н қажет етеді;

в), с) хештеу стратегиясының қолайлы параметрлерін таңдауда хеш- кecтeci жолының барлық нөмірлері, яғни {0,1,2,...,m-1} жиынының элементтері хеш-кестесінің мәндерімен анықталатынын дәлелдеу мумкіндігінің бар болуын қажет етеді. Бұл хештеу стратегиясының нұсқалары ушін mod функциясын анықтау және нактылау қажет.

Тиімділік бағалары квадраттық хештеу ушін де белгілі.

Хеш-кестеде бар элементті iздey барысындағы квадраттық хештеудің орта санының бағасы мынандай түрде болады:

1 - ln(1 - α) - α / 2

Ал хеш-кестеде жок элементті іздеу барысындағы квадраттық хештеудің орта санының бағасы мынандай түрде болады:

1/(1- α)- α-ln(1- α)

33. Хеш-функциялар және хеш-кестелер

Бұл әдістің мәні 1 қадамда блок адресін(физикалық түрде х-қа тең ізделінді жол мағынасымен ізделінетін жазба осында болады) анықтауға мүмкіндік беретін k=f(x) функционалдық тәуелділігін табуда. Алайда мұндай есептің қойылымы жалпы жағдайда шешімсіз. Сондықтан да хэш-кестені қолдануға тура келеді. Хэш-кесте hash массивінен тұрады: hash[m]=k, мұндағы k – х-қа тең ізделінді жол мағынасымен ізделінетін жазба сақталатын блок адресі

m=h(x), h(x) – 1 қадамда табылатын қандай да бір функция ж/е ол хэш-функция д.а.

Хэш алгоритмі келесі түрде болады:

m:=h(x); k:=hash[m];

Әрине, іздеу жасамас бұрын алдымен хэш-кестені құрып алу қажет:

for ∈ x {іздеу мәндерінің жиыны} do hash[h(x)]:=block(x); // block(x) – х-қа тең іздеу жолы бар жазба сақталатын

А)∀ х,у [ (h(x)=h(y)) –> (x=y)]- инъективті шарт

В)∀ m ∈ {m} ∃ x h(x)=m –сюръективті шарт

B шарты С шартына эквивалент екенін байқаймыз:

С) ∀ х h(x)=1..n т.е. ({m}=1..n)

A) Кез келген x,y (h(x)=h(y)=>x=y) – инъективті шарт.

B) {m} жиынындағы кез келген m үшін x табылады, h(x)=m. –сюръективті шарт.

B шарты С шартына эквивалент екенін байқаймыз:

С) кез келген х - h(x)=1..n ({m}=1..n), егер х-тің барлық эл-ті әртүрлі ж/е A шарты орындалса.

Хэш-функция кілт/ді кесте адрес/не бірдей етіп бөлуді қамтамасыз етеді, алайда 2 түрлі кілтке бір адрес сәйкес келуі мүмкін. Егер адрес бос болмаса, коллизия деп аталатын жағдай пайда болады. Оны жою алгоритмі: келесі ұяшыққа тексеру жүргізіледі, өз ұяшығын таппағанша. Элемент кілтімен осы ұяшыққа орналасады.

Іздеуге де осыған ұқсас алгоритм қолд-ды: кілтке сәйкес келетін хэш-ф-я-ң мәні таб-ды, көрс-ген адрес б-ша кестенің эл-ті текс-ді. Егер бос ұяшық таб-са, онда эл-т жоқ.

Хэш-кестенің өлшемі орналасатын эл-терден көп болуы керек. Егер кесте 60 %-ке толған болса, практика көрсеткендей, жаңа эл-т үшін екі ұяшықтан көп емес ұяшықтар тексеріледі. Эл-т өшірілген соң, жады көлемі қайта қолдануға жатпайды.

Хэш алгоритмінің қарапайым алгоритмі - f(k)єk (mod 10), k - кілт, бүтін сан (1 кесте)

1 кесте Прямой метод доступа

Исходные ключи	Преобразованные объектные ключи	Адрес хранения (относительный № блока)
X101 X102 X103... X199 Y100 Y101	01 02 03... 99 100 101	01 02 03... 99 100 101	X101 X102 X103... X199 Y500 Y501

Алайда бұл функ-я бірқалыпты теңдей бөлуді қамтамасыз етпейді, сондықтан басқа да сәйкес функ-р қолд-ды, м/лы f = сумма цифр ключа (mod 10)+1.

34. Қос хештеу және оның ерекшеліктері

Қос хештеу тәсілінде дәстүрлі екі хеш-функция қолданылады: оның біріншісі хеш-кестесінің жолының нөмірін алғашқы әрекетте анықтауда қолданылатын h(p) хеш-функциясы; екіншісі h⁰(p) хеш-функциясы коллизия жағдайында сынақтарды реттеуде қолданылады, сондықтан:

{ xmodm |x=(h(p) + i*h₀(p)), i=0,1,2,…,m-1}, (**)

Әр түрлі і үшін жасалған есептеулерден мына сынақтар тізбегін аламыз:

h(p), (h(p) + h⁰(p)) modm, (h(p) + 2 h⁰(p)) modm,..., (h(p) + (m-1) h⁰(p)) modm, …

Бұдан жаңа хеш-функция жазбасындағы екінші қосылғыштың тек қана сынақ нөміріне ғана емес сонымен қатар, оның кілтіне де тәуелді екенін көруге болады. Және де бұл жағдай әр түрлі екі кілттер үшін сынақтар тізбегі ерекшеленетінінне негіз болады деуге болады. h⁰ функциясының қолайлы таңдалынуы оның сапасын қаматамасыз етеді, және мұндағы m жай сан болуы тиіс. Қос хештеудің хеш-функциясын анықтауына сүйеніп, егер кейбір p₂ кілт үшін кез-келген h(p)+і* h⁰(p) кездейсоқ бірінші есептелген мән болса, онда келесісі h(p) + (і+1)* h⁰(p) болмай, h(p)+і* h⁰(p)+ h⁰(p₂) болады.

Қос хештеу есептеудің күрделенуіне әкеледі, екінші жағынан колизияларды шешуде қолайлы тәсіл береді. Осыдан h⁰(p) функциясы күрделі есептелуі тиіс емес.

Жаттығу: (**) формуласы бойынша қос хештеуде h⁰ және m өзара жай сан болса, р кілті үшін (**) формуласымен анықталатын сынақтардың тізбегі хеш-кестесінің жолдарының {0,1,2,…,m-1} жиынын толық жабатынын дәлелдеу қажет.

h⁰(p) функциясы үшін [25] көрсетілгендей h⁰(p,і)=i*h(p)+1 деп алуға болады және де, егер h(p)=k деп белгілесек, онда ол келесі сынақтар тізбегін береді:

k, 2k+1, 5k+2, 10k+3, …, k+i*(i*k+1), …

Егер қандай да бір р кілті үшін алғашқы мәні р кілтінің бір сынақ мәнімен кездейсоқ бірдей болғаны анықталса, мысалы 2k+1, онда р кілтінің сынақтар тізбегі р кілтіне қарағанда өзгеше болады, дәлдеп айтсақ 2k+1, 4k+3, 10k+7, …, мұндағы соңғы есептеудің мәні келесі алғашқы формула негізінде алынған:

((h(p)+2h⁰(p))modm=(h(p)+2h⁰(p,2))modm=(10k+7)modm

Ендігі кезекте хеш-функциясын таңдауымыз қақтығысқа әкелмейді деп үміттеніміз. Алайда 2h⁰(p,і)=i*h(p)+1 түрінде таңдалған хеш-функциялы (**) хештеу схемасын қолдану мәндерінің жан-жақтылығына қарамастан біршама шектелген.

Қос хештеуді қорыта келе, бұл тәсілде хештеу функциясын күрделендіру арқылы екінші кластерлердің проблемаларын болдырмауға әкелетінін көруге болады. Қос хештеу процедурасының қолайлылығы бағалаулармен де нақтыланады.

1/а * ln(1/(1-a)) бағасы хеш-кестеде бар элементтерді іздеу сынақтарының ортаңғы санын береді.

1/(1-а) бағасы хеш-кестесіне жаңа элементті қойғандағы сынақтардың ортаңғы санын береді. Бұл баға хеш-кестеде элемент жоқ жағдайда да іздеуде сақталынып қалады. Бұл бағаларды сызықтық хештеу мен төртбұрыштық хештеу бағаларымен салыстыру да қызығушылық туғызады.

35. Cocktail sort және оның ерекшеліктері

Көпіршіктік сұрыптаудың бір түрі.Көпіршіктік сұрыптаудың әдісін талдай отырып 2 маңызды жайды айтып кеткен дұрыс:

- Біріншіден,массивті бөліп қарастырса,орын алмастыру жүрмей жатса онда бұл бөлігі сұрыпталған,сәйкесінше оны қарастырмаймыз.

- Екіншіден,массив соңынан басына қозғалыста min элемент 1 позицияға алдына қозғалады,ал max элемент 1 позиция оңға жылжиды.

Осы 2 жай көпіршіктік сұрыптаудың сұрыптаудың әдісіне ұқсас боп келеді.

Ауыстыру арқылы сұрыптау. N элементтен тұратын а массивін айырбастау арқылы сұрыптау үшін немесе көпіршік әдісімен сұрыптау үшін n-ші жүріс қажет. Әрбір жүрісте көршілес екі элемент салыстырылады және егер 1-сі үлкен болса немесе 2-не тең болса, онда бұл элементтер орындарымен ауысады. әрбір жүрістің аяғында ең кіші элемент ішкі тізімнің жоғарғы жағына көтеріліп отырады. Бұл қайнап жатқан судың ішіндегі ауаның көбікшесіне ұқсас. Сондықтан көпіршік әдісі деп аталады.

Мысал. Массив:

50,20,40,75,35

0-жүріс. 50 мен 20салыстырылады.

20,50,40,75,35

1-жүріс. 50 мен 40 салыстырылады

20,40,50,75,35

2-жүріс. 50 мен 70 реттелген, сондықтан қалады.

20,40,50,70,35

3-жүріс.75 пен 35 салыстырылады.

20,40,50,35,75

4-жүріс. 50 мен 35 салыстырылады

20,40,35,50,75

5-жүріс. 40 пен 35 салыстырылады

20,35,40,50,75

20 мен 30 реттелген

20,35,40,50,75 болып реттеледі.

Массивтегі жүрістер саны минимальды немесе максимальды элемент қай жерде орналасқанына байланысты. Мұнда бірінен кейін бірі келетін жүрістердің бағытын ауыстыру арқылы жылдамдатуға болады. Мұндай алгоритм Шейкер сұрыптауы деп аталады.

Есептеу күрделілігі. Массив реттелген болған жағдайда бүкіл тізім бойынша 1 ғана жүріс өтеді. Мұнда тиімділігі О(n)-ға тең. Ал ең тиімсіз жағдайда i-1 жүріс орындалады және i-ші жүрісте n-i-1 салыстыру жүргізіледі. Ең тиімсіз жағдайда тиімділігі О(n²) тең. Жалпы жағдайда таңдау арқылы сұрыптау көбікше арқылы сұрыптауға қарағанда ауыстырылатын сан аздығымен тиімді болады. Шейкер сұрыптау алгоритмі элементтердің барлығы немесе көпшілігі сұрыпталған жағдайда пайдаланған тиімді.

Шейкер сұрыптаудың Dev C++ программалау тілінде жазылған коды:

#include <stdio.h>

#include <conio.h>

#define try_swap { if (a[i] < a[i - 1])\

{ t = a[i]; a[i] = a[i - 1]; a[i - 1] = t; t = 0;} }

void cocktailsort(int *a, size_t len)

{ size_t i;

int t = 0;

while (!t) {

for (i = 1, t = 1; i < len; i++) try_swap;

if (t) break;

for (i = len - 1, t = 1; i; i--) try_swap;

}

}

int main()

{ int x[] = { 4,8,6,15,3,54,13,81,-8,49 };

size_t i, len = sizeof(x)/sizeof(x[0]);

cocktailsort(x, len);

for (i = 0; i < len; i++)

printf("%d\t", x[i]);

getch();

return 0;

}

36. AVL ағаштары және оның ерекшеліктері

Бинарлы ағаштардың бұл класы алдыңғы жағдайдағымен салыстырғандағы тұрғызу алгоритмі күрделі болғанымен маңызды позитивті қасиеттерге ие болады. Бұл тип ағаштар көзге бейсимметриялы көрінуі мүмкін, бірақ оларда ұзын бұтақтар жоқ, оны төменде келтірілген анықтаманы мұқият оқып шыққанда түсінуге болады. Мұндай ағаштың түбірінен шыққан бұтақтың максималды ұзындығы с*log2n, мұнда c=1.44 аспауы тиіс.

Екіншіден, элемент қосу немесе алудан кейін ағашты түгелдей қайта құру қажет емес, сонымен мұндай ағашты құру алгоритмі белгілі бір күрделіліктерге қарамай көп еңбекті талап етпейді.

AVL ағаштарды көбіне баланстандырылған ағаштар деп атайды.

V төбесінен басталатын ағаш бұтағының ұзындығы депосы бұтаққа тиісті төбе/ деңгейінің максималь деңгейі мен V төбесі деңгейі арасындағы айырма аталады. Сонымен, бұтақ ұзындығы деп осы бұтаққа тиісті ең ұзын жолдың ұзындығы алынады. Көбіне ұзындық атауының орнына қосымша ат биіктік қолданылады.

Ағаш төбесі балансы деп берілген төбелерден шығатын оң және сол бұтақтар ұзындықтарының айырмасын айтады.

Егер ағаштың әрбір төбесі үшін баланстың абсолют мәні 1-ден артық болмаса, онда ағашты баланстандырылған (AVL) ағаш деп атайды.

N элементтен тұратын массив бойынша тұрғызылған AVL ағаштағы ең ұзын бұтақтың ұзындығын бағалайық. Бұл үшін L≥1 санын белгілейміз, алдымен максималь ұзындығы L- ға тең бұтақтары бар AVL ағаштар жиынын қарастырамыз. Осы ағаштардың ішінде төбелер саны минимум болатындары да бар. Ары қарай бұл AVL ағаштарын минимальды деп атаймыз.

Енді біз мына функцияны қарастырайық.

n(l)-AVL ағашындағы төбелердің минималь саны, бұтақтарының максималь ұзындығы L≥1 тең. Бұл жерде Шеннон функциясын еске түсіруге болады, бірақ аналогиясы тура болмайды, себебі Шеннон функциясы maxmin функциясы, ал біздің жағдайда maxmin.

AVL ағашқа жаңа төбе қосу кезінде бинарлы ағашты тұрғызудың қарапайым алгоритмі қолданылады. Осылайша, бар болған AVL ағашқа қайта қосылған төбе, оны N арқылы белгілейік, ағаш түбірі мен жаңа төбені қосатын ерекшеленген деп аталатын жол үшін ақырғы төбе болып табылады. Жаңа төбелерді қосу ағаш балансын бұзатын жағдайда ағаштан N төбесі алған позиция ақырғы болмауы мүмкін. Жаңа төбе қосу кезінде тек ерекшеленген жол бойындағы төбелер балансы өзгеретінін ескерсек, онда қосқаннан кейін осы жол бойындағы төбелер балансын ғана қайта есептеу керек. Сонда егер олардың ең болмағанда біреуіндегі баланс мәні ± 2 тең болса, онда жартылай және онша қиын емес ағашты қайта тұрғызу жүргізу керек.