RB-властивості

Бінарне дерево називається червоно-чорним, якщо воно має наступні властивості:

1) кожна вершина або червона, або чорна,

2) корінь дерева – чорний,

3) кожний листок (NULL) – чорний,

4) якщо вершина червона, обидві його нащадки чорні,

5) усі шляхи від кореня до листків, мають однакову кількість чорних вершин.

Такі властивості надають червоно-чорному дереву додаткового обмеження: найдовший шлях із кореня до будь-якого листка перевищує найкоротший шлях не більше ніж вдвічі. У цьому сенсі таке дерево можна назвати збалансованим. Зважаючи на те, що час виконання основних операцій з бінарними деревами пошуку залежить від висоти, таке обмеження ґарантує їхню ефективність в найгіршому випадку, чого звичайні бінарні дерева ґарантувати не можуть.

Для того, щоби зрозуміти, чому перелічені властивості забезпечують існування такого обмеження, зазначимо, що в червоно-чорному дереві, відповідно до властивості 4, не існує такого шляху, на якому б зустрілися дві червоні вершини підряд. Найкоротший шлях складається з усіх чорних вершин, а в найдовшому червоні та чорні вершини чергуються. З врахуванням властивості 5, отримуємо, що глибина будь-яких двох листів відрізняється не більше ніж в два рази.

У деяких зображеннях червоно-чорних дерев, NULL-листки не наводяться, тому що вони не містять корисної інформації, але їхнє існування необхідне для забезпечення усіх властивостей.