Преди много време имаме двоично дърво. Но след това искаме да имаме по-добро двоично дърво за търсене на елементи, затова създадохме двоично дърво за търсене. Тогава хората откриха, че двоичното дърво за търсене има проблеми, тъй като дегенерираната му версия е свързан списък, а не дърво. И така, създадохме AVL дърво, което може да поддържа баланса на двоичното дърво за търсене. Но дървото AVL не е единственото решение за балансиране на дървото за двоично търсене. Има и друго дърво, наречено „дърво 2–3“, за да може операцията за търсене да бъде толкова бърза, колкото дървото за двоично търсене и да има идеята за свойството баланс от дървото AVL.
2–3 дърво: позволяваме на възлите да имат две или три деца, наречени 2-възли и 3-възли. Когато един възел има три деца, той съхранява два ключа.
Това 2-3 дърво изглежда странно и готино в същото време :)
Дърво от 2–3 с височина h е или: [1] празно (h = -1), [2] корен с 2 възела и две поддървета, всяко от неговото поддърво има височина h-1 и [3] корен с 3 възела и три поддървета, всяко от неговите поддърво има височина h-1. Важно е също така да знаете, че всички листа трябва да са на едно и също ниво на дървото.
2–3 дърво с n възли има височина O(log(n)). Така че операцията find(x) е бърза. Можем да използваме рекурсия, за да намерим x, но когато стигнем до 3-възел, трябва да проверим връзката между x и двете ключови стойности в този възел, за да решим кое от трите поддървета да посетим.
За нашите операции за вмъкване и изтриване ние временно разрешаваме „1-възел и 4-възела“. 1-възел има едно дете и няма ключове. 4-възел има четири деца и три ключа. Когато възникнат тези възли, ние ще ги заменим с 2-възли и 3-възли.
Нека видим структурата на възела и операцията за намиране:
class Node {
int nChildren; //number of children 2 or 3
Node child[3]; //children pointers
Key key[2];
Value value[2];
}
//how about 1-node and 4-nodes? Well, ignore them for now.They are just concepts,
//so in the actual implementation, we can detect that we are conceptually creating
//1-node and 4-nodes and then do something without actually creating them.
//Pseudocode for find. Start from tree's root node.
Value find(Key key, Node n) {
while (n != null) {
if (key == n.key[0]) {
return n.value[0]; //key found
} else if (n.nChildren == 2 || key < n.key[1]) {
n = n.child[0]; //go to left child
} else if (key == n.key[1]) {
return n.value[1];
} else {
n = n.child[1]; //go to middle child
}
}
return null;
}
//insert and delete is messy. I skip them.
Дървото 2–3 използва операции split(), merge() и adoption(), за да поддържа своя баланс. Нека видим как изглеждат по-долу:
За вмъкване: процесът е подобен на дървото за двоично търсене; обаче, когато се опитваме да добавим елемента в 3-възела, както на снимката по-горе, дясната част на сливането, вмъкваме k, за да го направим от [b:d] до [b:d:k] (концептуално), тогава ще трябва да балансираме отново дървото чрез извършване на разделяне.
Ето един пример;
Вмъкваме 7, както бихме направили в дърво за двоично търсене. И така, става 6:7:8. Но възелът става 4-възел (4 деца). Така че трябва да направим нещо по въпроса. Ние насърчаваме 7 до 3-възел 9:13. Но отново имаме 7:9:13. Така че повишете 9 до 2-възел 5, като извикате функцията split(node). Сега имаме 5:9, 3 възела, така че нищо не трябва да се променя, всичко е балансирано.
Нека сравним как вмъкването на 2–3 дърво е различно от AVL и дървото за двоично търсене.
Времето за изпълнение на операциите за намиране, вмъкване и изтриване за 2–3 дърво е O(log(n)).
За изтриване: Първо намираме ключа за изтриване като в двоично дърво за търсене. Ако не се появи в листен възел, тогава ние идентифицираме заместващ ключ като наследник по ред. Копираме заместващата двойка ключ-стойност, за да заменим изтрития ключов запис, и след това рекурсивно изтриваме заместващия ключ от неговото поддърво. Ключът за заместване винаги е на ниво напускане въз основа на свойството на дървото и е или максимумът, или минимумът на лявото или дясното поддърво. Правенето на това обаче изисква много рекурсия и много реконструкция на дървото 2–3, ако е необходимо. Твърде сложно.
И така, накратко, когато казваме, че изтриваме ключа от дърво 2–3, обикновено се приема, че винаги изтриваме листен възел, за да опростим алгоритъма за изтриване. Разбира се, винаги можете да опитате да изтриете вътрешните възли, просто е по-сложно.
Приемане (завъртане на ключове) и сливане при изтриване:
Трябва да поддържаме 2–3 дървото, за да бъде балансирано. Изтриваме възела (листовия възел), дървото не е балансирано. За да поддържате дървото балансирано:
Ако възелът е 1-възел и има ляв или десен брат, който е 3-възел, тогава ние приемаме най-левия или най-десния ключ и поддърво от този брат, което води до два 2-възела. Вижте пример 1 по-долу. (LOL, като осиновяване на дете).
Ако не можем да приемем, като вземем 1 ключ от братя на възела (1-възел), тогава сливаме 1-възел с този брат с 2 възела, за да образуваме 3-възел. Но тогава имаме нужда от ключ, за да завършим този 3-възел, така че вземаме този ключ от нашия родител. Ако родителят е бил 3-възел, сега той става 2-възел и ние сме добре. Ако родителят е бил 2-възел, той вече е станал 1-възел и процесът на преструктуриране продължава нагоре в дървото. И накрая, ако някога стигнем до корена на дървото, където 1-възел е коренът, тогава премахваме този корен и правим единственото му дете новия корен. Вижте пример 2 и 3 по-долу. (LOL, все едно да кажеш, че ние двамата сме самотни хора, нека бъдем заедно и да дадем чувството си за самота на други хора).
ДОБРЕ. За следващата статия ще говоря за червено-черни и AA дървета, които могат да бъдат получени от 2-3 дървета.
— Край на учебните ми бележки —
