5 страница. AVL ағашқа жаңа төбелер қосу есебі шешімін корректі түрде жүргізетін жалпы талаптарға тоқталып кетейік:

AVL ағашқа жаңа төбелер қосу есебі шешімін корректі түрде жүргізетін жалпы талаптарға тоқталып кетейік:

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

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

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

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

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

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

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