Червоно-чорне дерево: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Немає опису редагування |
|||
Рядок 30:
Такі властивості надають червоно-чорному дереву додаткового обмеження: найдовший шлях з кореня до будь-якого листа перевищує найкоротший шлях не більше ніж вдвічі. В цьому сенсі таке дерево можна назвати збалансованим. Зважаючи на те, що час виконання основних операцій з бінарними деревами пошуку залежить від висоти, таке обмеження гарантує їхню ефективність в найгіршому випадку, чого звичайні бінарні дерева гарантувати не можуть.
Для того, щоби зрозуміти, чому перелічені властивості забезпечують існування такого обмеження, зазначимо, що в червоно-чорному дереві, відповідно до властивості 4 не існує такого шляху, на якому б зустрілись дві червоні вершини підряд. Найкоротший шлях складається з усіх чорних вершин, а в найдовшому червоні та чорні вершини чергуються. З врахуванням властивості 5, отримуємо, що глибина будь-яких двох листів відрізняється не більше ніж
В деяких зображеннях червоно-чорних дерев, NIL-листки не наводяться, тому що вони не містять корисної інформації, але їхнє існування необхідне для забезпечення усіх властивостей.
| |||