Червоно-чорне дерево: відмінності між версіями

[перевірена версія][перевірена версія]
Вилучено вміст Додано вміст
зображення (чергування кольорів)
DixonDBot (обговорення | внесок)
м Додавання/виправлення дати для: Шаблон:Без джерел; косметичні зміни
Рядок 1:
[[Файл:RB-дерева_маленькі_приклади.png|thumb|right|У ЧЧ деревах червоні і чорні вершини необов'язково чергуються]]
'''Червоно-чорне дерево''' ({{lang-en|red-black tree}}, {{lang-en|RB tree}}) — в [[інформатика|інформатиці]] — різновид [[бінарне дерево пошуку|бінарного дерева пошуку]], вершини якого мають додаткові властивості (RB-властивості), зокрема «колір» (червоний або чорний). Червоно-чорні дерева — різновид [[збалансоване дерево|збалансованих дерев]], в яких за допомогою спеціальних трансформацій гарантується, що висота дерева ''h'' не буде перевищувати [[Нотація Ландау|O(''log n'')]]. Зважаючи на те, що час виконання основних операцій на бінарних деревах (пошук, видалення, додавання елементу) є O(''h''), ці структури даних на практиці є набагато ефективнішими, аніж звичайні бінарні дерева пошуку.
 
== RB-властивості ==
Рядок 41:
|}
 
''Зауваження:'' В наступних випадках ми припускаємо, вершина P є лівою дитиною G. Якщо P — права дитина, ''ліво'' та ''право'' в аналізі наступних випадків слід поміняти місцями.
 
{|
Рядок 58:
 
{{Datastructure-stub}}
{{Без джерел|дата=січень 2008}}
 
[[Категорія:Дерева (структури даних)]]