Червено-черно дърво Въведение


Ниво на трудност Трудно
Често задавани в Амазонка CodeNation Facebook Google Uber
Разширена структура на данните Двоично дърво за търсене Двоично дърво Структура на данни Дърво

Red Black Tree е самобалансиращо се двоично дърво. В това дърво всеки възел е или червен възел, или черен възел. В това Въведение за червено-черното дърво ще се опитаме да обхванем всички негови основни свойства.

Свойства на червено-черното дърво

  1. Всеки възел е представен като червен или черен.
  2. Коренният възел винаги е черен.
  3. Червеният възел не може да има червен родител или червено дете (т.е. няма два съседни червени възела).
  4. Всеки път от който и да е възел до неговия потомък NIL трябва да съдържа равен брой черни възли.

Валидни и невалидни примери за червено-черно дърво

Червено-черно дърво Въведение

Червено-черно дърво Въведение

Анализ на сложността на времето

Всички BST операции като търсене, вмъкване, изтриване и др. Могат да се извършват за O (h) време, където h е височината на червено-черното дърво, а за балансиран BST височината винаги е от порядъка дневник (n) [n-> брой възли].

Търсене = O (log (n))
вмъкване = O (log (n))
заличаване = O (log (n))

Черна височина в червено-черно дърво

Черната височина в червено-черно дърво се определя като броя на черните възли по простия път (не посещавате два възела два пъти) от който и да е възел до лист (който е NIL). Представен е с bh (x).

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

За разлика от AVL дърво, балансът на височината не е толкова строг, но при червено-черните дървета броят на ротациите е по-малък в сравнение с AVL дърветата.
Височина на червено-черно дърво h <= 2 (log (n + 1)) {Основата на регистрационния файл е 2} Подробно доказателство защо височината на RB дърветата е <= 2 log (n + 1).

За да поддържа баланса по височина, червено-черното дърво използва оцветяване и преструктуриране.

Можете да видите как RB дърветата се оцветяват и преструктурират тук.

Преоцветяване

Отнася се за промяна на цвета на някои червени възли на черен и обратно, това се прави винаги, когато братът и сестрата на червения родител на червен възел са червени.

Червено-черно дърво Въведение

 

преструктуриране

То се отнася до въртенето на дървото, прави се винаги, когато червено дете има червен родител и черен или нулев чичо. Има четири случая на преструктуриране,

  • прав
  • Left
  • Дясно ляво
  • Ляво, дясно

Приложения

  • Използва се в реални библиотеки за внедряване на самобалансиращи се BST.
  • Използван като TreeSet и TreeMap в JAVA и набори и карти в C ++.

Търсене

Червено-черното дърво е BST, така че търсенето в RBT е точно същото като търсенето в BST, цветът на възела няма значение.