Работа със структури от данни в C и Python, част 9

данни

Серия съдържание:

Това съдържание е част от поредица от статии: Работа със структури от данни в C и Python

Това съдържание е част от поредицата: Работа със структури от данни в C и Python

Следете за още статии от тази поредица.

Тази статия разглежда разнообразие от бинарни дървета за търсене - червено-черни дървета, които също се отнасят до балансирани дървета. Такива дървета се използват за решаване на различни задачи, например в един от планиращите ядра на Linux (напълно справедлив планировчик) или за създаване на асоциативни масиви. Статията, както обикновено, ще се занимава с характеристиките за изпълнение на червено-черните дървета и алгоритмите за работа с тях.

Червени и черни дървета

Червено-черното дърво е друга форма на балансирано двоично дърво за търсене. За първи път е представен през 1972 г. като друг вид балансирано двоично дърво. Времето за намиране, вмъкване или изтриване на възел за червено-черно дърво е логаритмична функция на броя на възлите.

Този тип дървета се различава от другите изпълнения по следните свойства:

  • всеки възел е свързан с определен цвят - червен или черен;
  • кореновият възел може да бъде от всякакъв цвят;
  • червените възли могат да имат само черни деца;
  • всички пътища от възел до който и да е лист отдолу в дървото съдържат същия брой черни възли.

Височината на червено-черно дърво, състоящо се от н възли, варира от двоичен логаритъм дневник (N + 1) до 2 * дневник (N + 1) .

Листинг 1 показва C структурите, описващи възлите на червено-черните и AVL дървета.

Листинг 1. Изходен код на възли, използвани в различни типове BST

Както можете да видите, структурата на AVL дървесен възел е много подобна на структурата, използвана за съхраняване на информация за червено-черен дървесен възел. Само фактор на баланса бал в червено-черно дърво, заменено с променлива червен, определяне на цвета на възела (червен или черен). Но функциите за вмъкване/изтриване на възли за червено-черно дърво са значително различни от тези за AVL дърво и трябва да се разглеждат отделно.

Също така, за да работите с червено-черно дърво, ви е необходима помощната структура от Листинг 2.

Листинг 2. Структура, описваща червено-черно дърво

Поставете възел в червено-черно дърво

Когато нов възел се вмъкне в цветно дърво (друго име за червено-черно дърво), той първоначално е настроен на червен. След това родителският възел се търси за добавения елемент и цветът му се проверява. Ако родителският цвят е черен, тогава се запазва основният критерий за дървото на цветовете. Ако родителят е червен, тогава се извършва итеративно (нерекурсивно) балансиране на дървото. В най-лошия случай времето за вмъкване може да достигне стойността на логаритъма от броя на възлите в червеното дърво.

За опростяване на алгоритъма се приема, че листата (възли без деца) са черни. Листинг 3 показва изходния код на функцията за определяне на цвета на възел.

Листинг 3. Функция за определяне на цвета на възел

За завъртане на възлите в дървото ще се използват функциите, показани в Листинг 4. Първата функция разменя два възела, втората функция изпълнява две такива суапове:

Листинг 4. Функции за въртящи се възли в червено-черно дърво

Листинг 5 показва изходния код на функцията за създаване на нов възел.

Листинг 5. Функция за създаване на нов възел

Когато вмъквате възел в цветно дърво, не е необходимо да прибягвате до рекурсия, тъй като това може да се направи за един проход. По принцип при вмъкване на нов възел са възможни три опции.

  1. настъпва смяна на цвета;
  2. изисква се един завой;
  3. изисква се двоен завой.

За да направите това, в допълнение към текущия възел, трябва да съхраните в паметта още три нива на дърво: "родител", "дядо" и "прадядо" на текущия възел.

Фигура 1. Поставяне на възел в червено-черно дърво.

работа