Червоно-чорне дерево Вступ  


Рівень складності Жорсткий
Часто запитують у Амазонка CodeNation Facebook Google Убер
Розширена структура даних Бінарне дерево пошуку Бінарне дерево Структура даних Дерево

Червоне чорне дерево - це самозбалансоване бінарне дерево. У цьому дереві кожен вузол є або червоним, або чорним. У цьому Вступі червоно-чорного дерева ми спробуємо висвітлити усі його основні властивості.

Властивості червоно-чорного дерева  

  1. Кожен вузол представлений як червоним, так і чорним.
  2. Кореневий вузол завжди чорний.
  3. Червоний вузол не може мати червоного батька чи дочірнього дочірнього (тобто немає двох сусідніх червоних вузлів).
  4. Кожен шлях від будь-якого вузла до його нащадка NIL повинен містити однакову кількість чорних вузлів.

Дійсні та недійсні приклади Червоно-Чорного дерева

Червоно-чорне дерево ВступPin

Червоно-чорне дерево ВступPin

Аналіз складності часу  

Усі операції BST, такі як пошук, вставка, видалення тощо, можуть виконуватися за час O (h), де h - висота червоно-чорного дерева, а для збалансованого BST висота завжди в порядку log (n) [n-> кількість вузлів].

Пошук = O (log (n))
вставка = O (log (n))
видалення = O (log (n))

Чорна висота в червоно-чорному дереві  

Висота чорного в червоно-чорному дереві визначається як кількість чорних вузлів на простому шляху (ви не відвідуєте той самий вузол двічі) від будь-якого вузла до аркуша (що є NIL). Він представлений bh (x).

Висота червоно-чорного дерева  

на відміну від AVL дерева, баланс висоти не такий суворий, але у червоно-чорних дерев число обертань менше, ніж у дерев AVL.
Висота червоно-чорного дерева h <= 2 (журнал (n + 1)) {Основа журналу 2} Детально доказ чому висота дерев RB становить <= 2 log (n + 1).

Дивись також
Рекурсія

Для підтримки рівноваги по висоті червоно-чорне дерево використовує перефарбовування та реструктуризацію.

Ви можете бачити, як дерева RB перефарбовуються і реструктуруються тут.

Перефарбовування

Це стосується зміни кольору деяких червоних вузлів на чорний і навпаки, це робиться всякий раз, коли рідний брат червоного батька червоного вузла є червоним.

Червоно-чорне дерево ВступPin

 

Реструктуризація

Це стосується обертання дерева, це робиться, коли у червоної дитини є червоний батько і чорний чи нульовий дядько. Є чотири випадки реструктуризації,

  • правий
  • Ліве
  • Праворуч ліворуч
  • Ліво право

Pin

додатків

  • Використовується в реальних бібліотеках для реалізації самозбалансованих BST.
  • Використовується як TreeSet і TreeMap в JAVA та набори та карти в C ++.

Пошук

Червоно-чорне дерево - це BST, тому пошук у RBT - це точно те саме, що пошук у BST, колір вузла не має значення.