Page 52 - 6110

час виконання основних операцій на бінарних деревах (пошук,
видалення, додавання елементу) є Т(h), ці структури даних на
практиці є набагато ефективнішими, аніж звичайні бінарні дерева
пошуку.
Бінарне дерево називається червоно-чорним, якщо воно має
наступні властивості (рис.11.6):
- кожна вершина або червона, або чорна;
- корінь дерева – чорний;
- кожний лист (NIL) – чорний;
- якщо вершина червона, обидві її дитини чорні;
- усі шляхи від кореня до листків, мають однакову кількість
чорних вершин.
Такі властивості надають червоно-чорному дереву додаткового
обмеження: найдовший шлях з кореня до будь-якого листа
перевищує найкоротший шлях не більше ніж в двічі. В цьому сенсі
таке дерево можна назвати збалансованим. Зважаючи на те, що час
виконання основних операцій з бінарними деревами пошуку
залежить від висоти, таке обмеження гарантує їхню ефективність в
найгіршому випадку, чого звичайні бінарні дерева гарантувати не
можуть.
Для того, щоб зрозуміти, чому перелічені властивості
забезпечують існування такого обмеження, зазначимо, що в
червоно-чорному дереві, відповідно до властивості “якщо вершина
червона, обидві її дитини чорні” не існує такого шляху, на якому б
зустрілись дві червоні вершини підряд. Найкоротший шлях
складається з усіх чорних вершин, а в найдовшому червоні та чорні
вершини чергуються. З врахуванням властивості “усі шляхи від
кореня до листків, мають однакову кількість чорних вершин”,
отримуємо, що глибина будь-яких двох листів відрізняється не
більше ніж в два рази.
В деяких зображеннях червоно-чорних дерев, NIL-листя не
наводяться, тому що вони не містять корисної інформації, але їх
існування необхідне для забезпечення усіх властивостей.

51