Чырвона-чорныя дрэвы: апісанне, асаблівасці

Рудольф Баер распрацаваў сістэму "чырвона-чорныя дрэвы" яшчэ ў пачатку 1970-х гадоў. Назва ж гэтай ёй далі Л. Гимпас і Р. Сэджвік.

Што за чырвона-чорныя дрэвы

Варта адзначыць, што яны з'яўляюцца адным відаў самобалансирующихся двайковых дрэў, якія забяспечваюць злічальны памер вышыні ад колькасці вузлоў і вырабляюць першасныя і базавыя працэсы дрэва пошуку за кароткі час. Да такіх аперацыях ставяцца далучэнне, выключэнне і подыскание вузла. Баланс забяспечваецца на базе дапаўненні атрыбуту прыкладнога абазначэння вузла, колеру. Гэта ўласцівасць бярэ на сябе адзін з верагодных канцэптаў і пазначаецца адным з згаданых кветак.

Колькасць чорных адзінак на галіны ад пачатку (кораня) да фіналу (ліста) называецца чорнай вышынёй дрэва.

ўзнікненне тэрміна

Апісваючы самобалансирующееся дрэва пошуку ў сваёй працы, аўтары артыкула, верагодна, нават не меркавалі, што стануць заснавальнікамі новага тэрміна. Тым не менш лёс распарадзіўся так, што ў друкарні меліся ў наяўнасці фарбы ўсяго двух колераў. Імі і абазначаўся кожны біт, далучайцеся да наступнаму вузлу.

прымяненне

У інфарматыцы чырвона-чорныя дрэвы прымяняюцца для фарміравання супастаўных дадзеных, да якіх могуць ставіцца разнастайныя вытрымкі і часткі надпісаў або лічбаў.

Стварыць можна чырвона-чорнае дрэва на Actionscript, Python, C ++ і практычна любой іншай мове праграмавання. Гэта вельмі проста. Чырвона-чорнае дрэва Java таксама досыць шырока распаўсюджана.

асаблівасці

Чорна-чырвоныя дрэвы ўяўляюць сабой дрэвы пошуку ў двайковай сістэме каардынатаў. У гэтых сістэмах у любога вузла ёсць пэўнае значэнне колеру. Яно можа браць на сябе адно з вышэйзгаданых мелі наймення. Акрамя усіх ужывальных умоў да бінарным дрэве, да разгляданых намі разнавіднасцям, ўжываюцца яшчэ і такія правілы:

• Колер вузла з'яўляецца выключна адным з двух вышэйпералічаных. Іншых варыянтаў няма, гэта адбіваецца таксама і ў назве тэрміна.
• Корань дрэва заўсёды павінен афарбоўвацца чорным. Выключэння магчымыя, аднак такое адступленне ад правіла дадае рызыка таго, што саб'е самобалансировка дрэва.
• Усё лісце маюць нулявое значэнне (NIL) і абазначаюцца чорным колерам.
• Неабходна сачыць, каб два сына кожнага чырвонага бацькоўскага вузла былі чорнымі.
• Любы лёгкі курс ад канкрэтнага вузла да ўсякага ліставога даччынага вузла забяспечвае дакладна роўная колькасць чорных структурных адзінак.

Часам чырвона-чорныя дрэвы інтэрпрэтуюць ў якасці банальных бінарных дрэў пошуку. Іх адрознення вызначаюць толькі тым, што ўзамен пэўных каляровых вузлоў, у вышэйзгаданыя значэння расквечаны рэбры.

Чаму выбіраюць менавіта чырвона-чорныя дрэвы

Чорна-чырвоныя дрэвы ўяўляюць сабой адзін з самых распаўсюджаных варыянтаў самастойна балансуе бінарных древ пошуку, да якіх найбольш часта звяртаюцца ў практычным стаўленні.

Чым тлумачыцца такая іх папулярнасць? Практыка гультаяватая, і гэта варта прызнаць. Усё, што занадта грувастка і цяжка ў выкарыстанні і пры гэтым дае параўнальна аналагічны вынік пры прымяненні больш простых метадаў, адмірае або сыходзіць на далёкі план. Такая распаўсюджанасць у народзе чырвона-чорных дрэў тлумачыцца тым, што яны найбольш часта забяспечваюць аптымальнае раўнавагу паміж якасцю і ўзроўнем збалансаванасці і выкручастым яго падтрымання.

Напрыклад, калі супастаўляць іх з дасканалымі ў ступені сваёй збалансаванасці дрэвамі, то можа ўзнікнуць сітуацыя, калі назіраецца, што «ідэальныя» прадстаўнікі накладваюць залішне непрымірымыя патрабаванні. А ва ўмовах увасаблення ў жыццё дзеянняў выключэння з дрэва або развароту занадта вялікая колькасць часу і сіл затрачваецца на стабілізацыю патрэбнай у дадзенай сітуацыі збалансаванасці.

працэсы

Працэс вычыткі чорна-чырвоных бінарных дрэў практычна аналагічны для ўсіх іншых двайковых разгалінаванняў пошуку. Гэта дакладна, паколькі любое чорна-чырвонае дрэва ўяўляе сабой адзін з прыватных варыянтаў класічнага бінарнага дрэва пошуку.

Аднак пры працы з імі варта ўлічваць вялікую верагоднасць таго, што прамое вытворчасць дзеянні ўключэння або выключэння дадзеных можа выклікаць пашкоджанне структуры чорна-чырвоных дрэў. Вялікай перавагай з'яўляецца тое, што для рэканструкцыі уласцівасцяў неабходна адносна малая колькасць дзеянняў, такіх як змяненне кветак і часцяком меней трох паваротаў дрэва. Фактычна ўсе гэтыя аперацыі не займаюць шмат часу.

Прыступаць да выканання дзеяння ўстаўкі або ўключэння элемента стаіць з прырашчэння наступнага вузла. Гэтая функцыя аналагічная ва ўсіх бінарных дрэве пошуку. Наступным крокам з'яўляецца колоризация вузла ў чырвоны. Адзіным адрозненнем можна лічыць тое, што калі пры выкананні ўстаўкі ў бінарным дрэве пошуку перш за ўсё прыбаўляем ліст, то ў чорна-чырвоным апошнія не нясуць ніякай інфармацыі. Такім чынам, замест іх дадаецца ўнутраны вузел, які прымае чырвоны колер і два яго чорных нашчадка.

Далейшыя нашы дзеянні наўпрост абумаўляюцца колерам прылеглых вузлоў. Для іх ужываюць тэрмін «дзядзька». Прамая аналогія з генеалагічным дрэвам. такім чынам:

• Характарыстыка таго, што ўсё лісце захоўваюць чорны колер, павінна рэалізоўвацца заўсёды.
• Паслядоўнасць таго, што два вытворных кожнага чырвонага вузла захоўваюць чорны колер, можа перапыніцца. Але адбываецца гэта толькі пры даданні чырвонага вузла, пры змене колеру чорнага на чырвоны або пры развароце усяго дрэва.
• Таксама адзначым, што паслядоўнасці ад вузла да ліста, якія ўключаюць адно і тое ж колькасць чорных вузлоў, могуць быць парушаныя. Гэта адбываецца толькі пры ўключэнні чорнага вузла, змене чырвонага элемента на чорны, а таксама ў процілеглым сітуацыі перафарбоўвання чорнага ў чырвоны. Гэта ж можа выконвацца і пры развароце дрэва.

Вывучыўшы ўсё вышэйпададзенае, нескладана разабрацца, як ажыццяўляецца пошук у чырвона-чорным дрэве.

Цікавая інтэрпрэтацыя такога простага паняцця, як дрэва, з апісаннем яго колеру - чырвона-чорнага або чорна-карычневага. Цяпер вы дасведчаныя і ў гэтым.