Червоно-чорне дерево: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м робот косметичні зміни |
Xqbot (обговорення | внесок) м робот змінив: it:RB-Albero; косметичні зміни |
||
Рядок 4:
Бінарне дерево називається червоно-чорним, якщо воно має наступні властивості:
# кожна вершина або червона, або чорна
# корінь дерева — чорний
# кожний лист (NIL) — чорний
# якщо вершина червона, обидві її дитини чорні
# усі шляхи від кореня до листів мають однакову кількість чорних вершин
[[Файл:Red-black tree example.svg|450px|center|Червоно-чорне дерево]]
Рядок 25:
Процедура починається аналогічно вставці елементу в бінарне дерево пошуку та фарбування її у червоний колір. Подальші дії залежать від кольорів сусідніх вершин.
Зазначимо, що:
* властивість 2 завжди зберігається
* властивість 3 порушується тільки при вставці червоної вершини, перефарбуванні чорної вершини в червону або обертанні
* властивість 4 порушується тільки при вставці чорної вершини, перефарбувані червоної вершини в чорну або обертанні
На допоміжних діаграмах, вершина, яка додається, позначена N, первісний батько цієї вершини позначений P, батько вершини P ("дідусь" N) позначений G. "Дядько" N (тобто вершина, яка має спільного з P батька — G) позначений як U. Розглянемо наступні випадки:
Рядок 72:
[[hr:Crveno-crno stablo]]
[[id:Pohon merah-hitam]]
[[it:
[[ja:赤黒木]]
[[ko:레드-블랙 트리]]
| |||