Является ли Red-Black tree сбалансированным

Я изучаю красно-черные деревья, и я читаю книгу «Введение в алгоритмы» Кормена. Теперь я пытаюсь создать красно-черное дерево с цифрами 1-10, используя псевдокод, описанный в книге - RB-INSERT-FIXUP (T, z). Вот скриншот enter image description here Является ли Red-Black tree сбалансированным

Все было нормально, пока я не вставил цифру «6» в дерево. Согласно псевдокоде я получаю следующий результат

enter image description here

Как вы можете видеть все красно-черные требования деревьев встречались, но я смущен, потому что я знаю, что красно-черное дерево должно быть сбалансировано на каждом шагу.

Я могу вручную выполнить процедуру «с левым поворотом» с помощью «2» и «4» и изменить цвета. В таком случае я получаю следующий результат, который уравновешивается соответствующего

enter image description here

Так что мой вопрос:

Это нормально иметь неравные дерева ?, или я что-то пропустил во время вставки узлов?

источник

2015-02-15 Ashot Khachatryan

Я думаю, что дерево rb может стать неуравновешенным до 2 log n в глубину. вы должны это проверить. идеально сбалансированное дерево грубо логарифмически n в глубину. неуравновешенность в rb-древе не так плоха, чтобы испортить ее большую O для различных операций. – thang

Это прекрасно. Красно-черные деревья сбалансированы, но не обязательно идеально. Если быть точным, свойства красно-черного дерева гарантируют, что самый длинный путь к листу (неявный, не показан на картинке) не более чем вдвое длиннее кратчайшего. Самая короткая имеет длину 2 (2 -> 1 -> лист), самая длинная имеет длину 4 (2 -> 4 -> 5 -> 6 -> лист), поэтому инвариант действительно выполняется.

источник

2015-02-15 21:04:52

Спасибо за ответ. Я только подумал, почему мы не всегда балансируем дерево, если это возможно (как в случае, о котором я упоминал). Тогда я думаю, что это повлияет на сложность. –

Да, rb-tres кажутся отличным балансом между ... балансом и скоростью :) Существуют и другие схемы балансировки - например. Дерево AVL гарантирует более сбалансированное дерево с той же сложностью, но хуже константы. Похоже, на практике это мало используется. –

@ MarcinŁoś Можете ли вы взглянуть на мой метод удаления RedBlackTree? http://stackoverflow.com/questions/28705454/how-to-fix-remove-in-redblacktree-implementation – committedandroider

Является ли Red-Black tree сбалансированным

ответ

Смежные вопросы