Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
У програмуванні збалансоване дерево в загальному розумінні цього слова — це такий різновид двійкового дерева пошуку, яке автоматично підтримує свою висоту, тобто кількість рівнів вершин під коренем є мінімальною.
Загальні відомості
Швидкість роботи більшості операцій на деревах залежить від висоти дерева. Такими операціями в першу чергу є:
- пошук вершини
- вставка вершини
- видалення вершини
Швидкість цих операцій напряму залежить від висоти дерева -- O(Height). Якщо говорити про залежність між кількістю вершин в дереві та його висотою, то висота дерева лежить у таких межах:
- H = N Висота дерева дорівнює кількості вершин у дереві, якщо дерево є виродженим.
- H = log(N) Висота дерева дорівнює логарифму, якщо дерево є повним.
Збалансованість дерева є важливою саме тому, що час виконання більшості алгоритмів на двійкових деревах пошуку є пропорційний до їхньої висоти. Звичайні двійкові дерева пошуку можуть мати досить велику висоту в тривіальних ситуаціях, що від’ємно впливає на швидкість виконання операцій.
Процедура зменшення (балансування) висоти дерева виконується за допомогою трансформацій, відомих як обернення дерева, у певні моменти часу (переважно при видаленні або додаванні нових елементів).
Ступені збалансованості
Ідеально збалансоване дерево
Ідеально збалансоване дерево — це дерево, у якого для кожної вершини різниця між висотами лівого та правого піддерев не перевищує одиниці[ ][]. Однак, така умова може вимагати значної перебудови дерева при додаванні або видаленні елементів, тому їх застосовують лише для пошуку, коли дані в них практично незмінні.
АВЛ-збалансованість
При додаванні в дерево нових вузлів або внаслідок їх вилучення ідеальна збалансованість втрачається. Дерево можна перебудувати, але така операція триває досить довго. Тому було запропоновано слабші вимоги щодо збалансованості, які отримали назву АВЛ-збалансованості. Дерево є АВЛ-збалансованим, якщо висоти лівого та правого піддерев різняться не більше, ніж на одиницю. Дерева, що задовольняють таким умовам, називають АВЛ-деревами (за прізвищами їх винахідників — Адельсон-Вельського і Ландіса). Зрозуміло, що кожне ідеально збалансоване дерево є також АВЛ-збалансованим, але не навпаки.
Див. також
Джерела
- Адельсон-Вельський, Ландіс, 1962, с. 263—266.
Посилання
- Гудзь Р. В., Ярошко С. А. Використання динамічних структур даних у програмах на Borland Pascal: Тексти лекцій. — Львів : Ред.-вид. відділ ОЦ ЛНУ ім. І. Франка, 2000.
- Г. М. Адельсон-Вельський. Один алгоритм организации информации / Г. М. Адельсон-Вельський, Е. М. Ландис // Докл. АН СССР. — 1962. — Т. 146, № 2. — С. 263–266.(рос.)
 | Це незавершена стаття про інформаційні технології. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U programuvanni zbalansovane derevo v zagalnomu rozuminni cogo slova ce takij riznovid dvijkovogo dereva poshuku yake avtomatichno pidtrimuye svoyu visotu tobto kilkist rivniv vershin pid korenem ye minimalnoyu Priklad nezbalansovanogo dereva Te same derevo pislya balansuvannya Zagalni vidomosti Shvidkist roboti bilshosti operacij na derevah zalezhit vid visoti dereva Takimi operaciyami v pershu chergu ye poshuk vershini vstavka vershini vidalennya vershini Shvidkist cih operacij napryamu zalezhit vid visoti dereva O Height Yaksho govoriti pro zalezhnist mizh kilkistyu vershin v derevi ta jogo visotoyu to visota dereva lezhit u takih mezhah H N Visota dereva dorivnyuye kilkosti vershin u derevi yaksho derevo ye virodzhenim H log N Visota dereva dorivnyuye logarifmu yaksho derevo ye povnim Zbalansovanist dereva ye vazhlivoyu same tomu sho chas vikonannya bilshosti algoritmiv na dvijkovih derevah poshuku ye proporcijnij do yihnoyi visoti Zvichajni dvijkovi dereva poshuku mozhut mati dosit veliku visotu v trivialnih situaciyah sho vid yemno vplivaye na shvidkist vikonannya operacij Procedura zmenshennya balansuvannya visoti dereva vikonuyetsya za dopomogoyu transformacij vidomih yak obernennya dereva u pevni momenti chasu perevazhno pri vidalenni abo dodavanni novih elementiv Stupeni zbalansovanosti Idealno zbalansovane derevo Idealno zbalansovane derevo ce derevo u yakogo dlya kozhnoyi vershini riznicya mizh visotami livogo ta pravogo pidderev ne perevishuye odinici sumnivno obgovoriti dzherelo Odnak taka umova mozhe vimagati znachnoyi perebudovi dereva pri dodavanni abo vidalenni elementiv tomu yih zastosovuyut lishe dlya poshuku koli dani v nih praktichno nezminni AVL zbalansovanist Pri dodavanni v derevo novih vuzliv abo vnaslidok yih viluchennya idealna zbalansovanist vtrachayetsya Derevo mozhna perebuduvati ale taka operaciya trivaye dosit dovgo Tomu bulo zaproponovano slabshi vimogi shodo zbalansovanosti yaki otrimali nazvu AVL zbalansovanosti Derevo ye AVL zbalansovanim yaksho visoti livogo ta pravogo pidderev riznyatsya ne bilshe nizh na odinicyu Dereva sho zadovolnyayut takim umovam nazivayut AVL derevami za prizvishami yih vinahidnikiv Adelson Velskogo i Landisa Zrozumilo sho kozhne idealno zbalansovane derevo ye takozh AVL zbalansovanim ale ne navpaki Div takozhAVL derevo B derevo Chervono chorne derevo Rozshiryuvane derevoDzherelaAdelson Velskij Landis 1962 s 263 266 PosilannyaGudz R V Yaroshko S A Vikoristannya dinamichnih struktur danih u programah na Borland Pascal Teksti lekcij Lviv Red vid viddil OC LNU im I Franka 2000 G M Adelson Velskij Odin algoritm organizacii informacii G M Adelson Velskij E M Landis Dokl AN SSSR 1962 T 146 2 S 263 266 ros Ce nezavershena stattya pro informacijni tehnologiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi