«Красно-черное дерево»



Download 156,31 Kb.
bet8/9
Sana15.06.2022
Hajmi156,31 Kb.
#672698
TuriЛитература
1   2   3   4   5   6   7   8   9
Bog'liq
ккрсано-черное дерево

Случай 1: N — новый корень. В этом случае, все сделано. Мы удалили один черный узел из каждого пути и новый корень является черным узлом, так что свойства сохранены.
void
delete_case1(struct node *n)
{
if (n->parent != NULL)
delete_case2(n);
}
Примечание: В случаях 2, 5, и 6 мы предполагаем, что N является левым потомком своего предка P. Если он — правый потомок, left и right нужно поменять местами во всех трех случаях. Опять-таки, примеры кода принимают это во внимание.


Случай 2: S — красный.



6. Сравнение с идеально сбалансированным АВЛ-деревом

6.1. Высота дерева


Пускай высота дерева h, минимальное количество листьев N. Тогда:

  • для АВЛ-дерева N(h) = N(h − 1) + N(h − 2). Поскольку N(0) = 1, N(1) = 1, N(h) растёт как последовательность Фибоначчи, следовательно N(h) = Θ(λh), где 

  • для красно-чёрного дерева 

Следовательно, при том же количестве листьев красно-чёрное дерево может быть выше АВЛ-дерева, но не более чем в  раз.[3]
6.2. Поиск
Поскольку красно-чёрное дерево, в худшем случае, выше, поиск в нём медленнее, но проигрыш по времени не превышает 39 %.

6.3. Вставка


Вставка требует до 2 поворотов в обоих видах деревьев. Однако из-за большей высоты красно-чёрного дерева вставка может занимать больше времени.

6.4. Удаление


Удаление из красно-черного дерева требует до 3 поворотов, в АВЛ-дереве оно может потребовать числа поворотов до глубины дерева (до корня). Поэтому удаление из красно-чёрного дерева быстрее, чем из АВЛ-дерева.

6.5. Память


АВЛ-дерево в каждом узле хранит высоту (целое число). Красно-чёрное дерево в каждом узле хранит цвет (1 бит). Таким образом, красно-чёрное дерево может быть экономичнее.
Однако, на практике в обоих типах деревьев используются целые числа, т.к. работа с битами требует дополнительных процессорных вычислений.

Download 156,31 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish