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

'''Червоно-чорне дерево''' ({{lang-en|red-black tree}}, {{lang-en|RB tree}}) — в [[інформатика|інформатиці]] — різновид [[бінарне дерево пошуку|бінарного дерева пошуку]], вершини якого мають додаткові властивості (RB-властивості), зокрема «колір» (червоний або чорний). Червоно-чорні дерева — різновид [[збалансоване дерево|збалансованих дерев]], в яких за допомогою спеціальних трансформацій гарантується, що висота дерева ''h'' не буде перевищувати [[Нотація Ландау|O(''log n'')]]. Зважаючи на те, що час виконання основних операцій на бінарних деревах (пошук, видалення, додавання елементу) є O(''h''n), ці структури даних на практиці є набагато ефективнішими, аніж звичайні бінарні дерева пошуку.