В следващия урок ще научим за структурата на данните на B Tree и ще обмислим нейното визуализиране.
java урок
И така, да започваме.
Какво е B дърво?
The Б Дърво е специален тип многостранно дърво за търсене , известен като М-път дърво, което се балансира само. Поради тяхната балансирана структура, тези дървета обикновено се използват за работа и управление на огромни бази данни и опростяване на търсенията. В B дърво всеки възел може да има най-много n дъщерни възела. B Tree е пример за многостепенно индексиране в система за управление на бази данни (СУБД). Листовите и вътрешните възли ще имат препратки към записи. Дървото B е известно като балансирано съхранено дърво, защото всички листови възли са на едно и също ниво.
Следващата диаграма е пример за B дърво:
Фигура 1. A B Дърво с ред 3
Разбиране на правилата на B дървото
Следните са важните свойства на B дърво:
- Всички листови възли са на едно ниво.
- Структурата на данните на B Tree се определя от термина минимална степен 'd'. Стойността на 'd' зависи от размера на дисковия блок.
- Всеки възел, с изключение на корена, трябва да се състои от поне d-1 ключа. Основният възел може да се състои от минимум 1 ключ.
- Всички възли (включително основния възел) могат да се състоят от най-много (2d-1) ключове.
- Броят на децата на възел е равен на добавяне на броя на наличните в него ключове и .
- Всички ключове на възел са сортирани във възходящ ред. Детето между два ключа, k1 и k2, се състои от всички ключове, вариращи съответно между k1 и k2.
- За разлика от бинарното дърво за търсене, структурата на данните на B дървото расте и се свива от корена. Докато двоичното дърво за търсене расте надолу и се свива надолу.
- Подобно на други дървета за самостоятелно балансирано двоично търсене, времевата сложност на структурата от данни на B дървото за операции като търсене, вмъкване и изтриване е O(log?n) .
- Вмъкването на възел в B дървото се случва само в листовия възел.
Нека разгледаме следния пример за B дърво от минимален ред 5.
Фигура 2. A B Дърво от ред 5
Забележка: Стойността на минималната поръчка е много повече от 5 в практически B Trees.
В горната диаграма можем да наблюдаваме, че всички листови възли са на едно и също ниво и всички нелистови възли нямат празно поддърво и се състоят от ключове с един по-малко от броя на техните деца.
Зададената формулировка на правилата на B Tree:
Всяко B дърво зависи от положително постоянно цяло число, известно като МИНИМУМ , който се използва, за да се определи броят на елементите от данни, които могат да се държат в един възел.
Правило 1: Коренът може да има само един елемент от данни (или дори никакви елементи от данни, ако също не е дъщерен); всеки друг възел има поне МИНИМУМ елементи от данни.
Правило 2: Максималният брой елементи от данни, съхранявани във възел, е два пъти по-голям от стойността на МИНИМУМ .
Правило 3: Елементите от данни на всеки възел на B дървото се съхраняват в частично попълнен масив, сортиран от най-малкия елемент от данни (на индекс 0 ) до най-големия елемент от данни (в крайната използвана позиция на масива).
Правило 4: Общият брой поддървета под възел, който не е лист, винаги е с един повече от броя на елементите от данни в този възел.
- поддърво 0, поддърво 1,...
Правило 5: По отношение на всеки възел, който не е лист:
- Елемент от данни в индекс е по-голям от всички елементи от данни в номер на поддърво аз на възела и
- Елемент от данни в индекс е по-малък от всички елементи от данни в номер на поддърво i+1 на възела.
Правило 6: Всяко листо в B дърво има еднаква дълбочина. По този начин се гарантира, че B Tree предотвратява проблема с небалансирано дърво.
Операции върху структура от данни на B дърво
За да се гарантира, че нито едно от свойствата на структурата от данни на B Tree не е нарушено по време на операциите, B Tree може да бъде разделено или съединено. Следват някои операции, които можем да извършим върху B дърво:
- Търсене на елемент от данни в B дърво
- Вмъкване на елемент от данни в B дърво
- Изтриване на елемент от данни в B Tree
Операция за търсене на B дърво
Търсенето на елемент в B Tree е подобно на това в Binary Search Tree. Но вместо да взема двупосочно решение (ляво или дясно) като двоично дърво за търсене, B дърво взема m-посочно решение във всеки възел, където m е броят на децата на възела.
Стъпки за търсене на елемент от данни в B дърво:
Етап 1: Търсенето започва от основния възел. Сравнете елемента за търсене, k, с корена.
Стъпка 1.1: Ако коренният възел се състои от елемента k, търсенето ще бъде завършено.
Стъпка 1.2: Ако елементът k е по-малък от първата стойност в корена, ще се преместим до най-лявото дете и ще търсим рекурсивно детето.
Стъпка 1.3.1: Ако коренът има само две деца, ще се преместим до най-дясното дете и ще търсим рекурсивно дъщерните възли.
Стъпка 1.3.2: Ако коренът има повече от два ключа, ще търсим останалите.
Стъпка 2: Ако елементът k не бъде намерен след обхождане на цялото дърво, тогава елементът за търсене не присъства в B дървото.
Нека визуализираме горните стъпки с помощта на пример. Да предположим, че искаме да търсим ключ k=34 в следното B дърво:
Фигура 3.1. Дадено B дърво
версии на android
- Първо ще проверим дали ключът k = 34 е в основния възел. Тъй като ключът не е в основата, ще преминем към неговите дъщерни възли. Можем също да наблюдаваме, че коренният възел има две деца; следователно ще сравним необходимата стойност между двата ключа.
Фигура 3.2. Ключът k не присъства в root - Сега, след като можем да забележим, че ключът k е по-голям от коренния възел, т.е. 30, ще продължим с дясното дете на корена.
Фигура 3.3. Ключът k > 30, преместете се вдясно дете - Сега ще сравним ключа k със стойностите, присъстващи на възела, т.е. съответно 40 и 50. Тъй като ключът k е по-малък от левия ключ, т.е. 40, ние ще се преместим в левия дъщерен елемент на възела.
Фигура 3.4. Ключът k<40, move to left child< li> - Тъй като стойността в лявото дете на 40 е 34, което е необходимата стойност, можем да заключим, че ключът е намерен и операцията за търсене е завършена.
Фигура 3.4. Ключът k = 34, лявото дете на 40
Сравнихме ключа с четири различни стойности в горния пример, докато го намерим. По този начин времевата сложност, необходима за операцията за търсене в B дърво, е O(log?n) .
Вмъкване на операция в B дърво
Докато вмъкваме елемент от данни в B Tree, първо трябва да проверим дали този елемент вече присъства в дървото или не. Ако елементът от данни е намерен в дървото B, тогава операцията по вмъкване не се извършва. Ако обаче това не е така, ще продължим с вмъкването. Има два сценария, които трябва да бъдат разгледани, докато вмъквате елемент в листовия възел:
Стъпки за вмъкване на елемент от данни в B дърво:
Етап 1: Ще започнем с изчисляване на максималния брой ключове във възела въз основа на реда на B дървото.
Стъпка 2: Ако дървото е празно, се разпределя основен възел и ние ще вмъкнем ключа, който действа като основен възел.
Стъпка 3: Сега ще търсим приложимия възел за вмъкване.
Стъпка 4: Ако възелът е пълен:
Стъпка 4.1: Ще вмъкнем елементите от данни във възходящ ред.
Стъпка 4.2: Ако елементите от данни са по-големи от максималния брой ключове, ще разделим пълния възел на медианата.
Стъпка 4.3: Ще бутнем средния клавиш нагоре и ще разделим левия и десния клавиш като ляво и дясно дете.
Стъпка 5: Ако възелът не е пълен, ще вмъкнем възела във възходящ ред.
Нека визуализираме горните стъпки с помощта на пример. Да предположим, че от нас се изисква да създадем B Tree от ред 4. Елементите от данни, необходими за вмъкване в B Tree са 5,3,21,11,1,16,8,13,4 и 9 .
- Тъй като m е равно на 3, максималният брой ключове за възел = m-1 = 3-1 = 2 .
- Ще започнем с вмъкване 5 в празното дърво.
Фигура 4.1. Вмъкване 5 - Сега ще вмъкнем 3 в дървото. Тъй като 3 е по-малко от 5, ще вмъкнем 3 отляво на 5 в същия възел.
Фигура 4.2. Вмъкване 3 - Сега ще вмъкнем 21 в дървото и тъй като 21 е по-голямо от 5, то ще бъде вмъкнато вдясно от 5 в същия възел. Въпреки това, тъй като знаем, че максималният брой ключове във възела е 2, един от тези ключове ще бъде преместен към възел по-горе, за да бъде разделен. По този начин 5, средният елемент от данни, ще се премести нагоре, а 3 и 21 ще станат съответно негов ляв и десен възел.
Фигура 4.3. Вмъкване 21 - Сега е време да вмъкнете следващия елемент от данни, т.е. 11, който е по-голям от 5, но по-малък от 21. Следователно 11 ще бъде вмъкнато като ключ отляво на възела, състоящ се от 21 като ключ.
Фигура 4.4. Вмъкване 11 - По същия начин ще вмъкнем следващия елемент от данни 1 в дървото и както можем да видим, 1 е по-малко от 3; следователно той ще бъде вмъкнат като ключ отляво на възела, състоящ се от 3 като ключ.
Фигура 4.5. Вмъкване 1 - Сега ще вмъкнем елемент от данни 16 в дървото, което е по-голямо от 11, но по-малко от 21. Въпреки това, броят на ключовете в този възел надвишава максималния брой ключове. Следователно възелът ще се раздели, премествайки средния ключ към корена. Следователно 16 ще бъде вмъкнато отдясно на 5, разделяйки 11 и 21 на два отделни възела.
Фигура 4.6. Вмъкване 16 - Елементът от данни 8 ще бъде вмъкнат като ключ отляво на 11.
Фигура 4.7. Вмъкване 8 - Ще вмъкнем 13 в дървото, което е по-малко от 16 и по-голямо от 11. Следователно елемент от данни 13 трябва да бъде вмъкнат отдясно на възела, състоящ се от 8 и 11. Въпреки това, тъй като максималният брой ключове в дървото може бъде само 2, ще се извърши разделяне, премествайки средния елемент от данни 11 към горния възел и 8 и 13 в два отделни възела. Сега горният възел ще се състои от 5, 11 и 16, което отново надвишава максималния брой ключове. Следователно ще има друго разделяне, което ще направи елемента от данни 11 коренния възел с 5 и 16 като негови деца.
Фигура 4.8. Вмъкване 13 - Тъй като елементът от данни 4 е по-малък от 5, но по-голям от 3, той ще бъде вмъкнат отдясно на възела, състоящ се от 1 и 3, което отново ще надвиши максималния брой ключове в даден възел. Следователно отново ще се появи разлив, премествайки 3 в горния възел до 5.
Фигура 4.9. Вмъкване 4 - Най-накрая елементът от данни 9, който е по-голям от 8, но по-малък от 11, ще бъде вмъкнат отдясно на възела, състоящ се от 8, като ключ.
Фигура 4.10. Вмъкване 9
В горния пример извършихме различни сравнения. Първата стойност беше директно вмъкната в дървото; след това всяка стойност трябваше да бъде сравнена с наличните възли в това дърво. Времевата сложност за операцията по вмъкване в B дърво зависи от броя на възлите и .
Изтриване на операция върху B дърво
Изтриването на елемент от данни на B Tree съдържа три основни събития:
java обратен низ
- Търсене на възела, където съществува ключът за изтриване,
- Изтриване на ключа и
- Балансиране на дървото, ако е необходимо.
Докато изтривате елемент от дървото, може да възникне състояние, известно като Underflow. Underflow възниква, когато възел се състои от по-малко от минималния брой ключове; трябва да държи.
Следват някои термини, които трябва да бъдат разбрани, преди да визуализирате операцията за изтриване/премахване:
Следват три видни случая на операцията за изтриване в B дърво:
Случай 1: Изтриването/Премахването на ключа се намира в листовия възел - Този случай е допълнително разделен на два различни случая:
1. Изтриването/премахването на ключа не нарушава свойството на минималния брой ключове, които възелът трябва да притежава.
Нека визуализираме този случай с помощта на пример, в който ще изтрием ключ 32 от следното B дърво.
Фигура 4.1: Изтриване на ключ на листов възел (32) от B дърво
Както можем да забележим, изтриването на 32 от това дърво не нарушава горното свойство.
2. Изтриването/премахването на ключа нарушава свойството за минималния брой ключове, които възелът трябва да притежава. В този случай трябва да вземем назаем ключ от неговия близък братски възел в реда отляво надясно.
Първо, ще посетим най-близкия ляв брат. Ако възелът на левия брат има повече от минималния брой ключове, той ще заеме ключ от този възел.
В противен случай ще проверим да вземем назаем от близкия десен братски възел.
Нека сега визуализираме този случай с помощта на пример, където ще изтрием 31 от горното B дърво. В този случай ще вземем назаем ключ от левия братски възел.
сортиране на списък с масиви
Фигура 4.2: Изтриване на ключ на листов възел (31) от B дърво
Ако и двата близки възела на брат вече се състоят от минимален брой ключове, тогава ще обединим възела или с левия възел или с десния. Този процес на сливане се извършва чрез родителския възел.
Нека визуализираме отново, като изтрием ключ 30 от горното B дърво.
Фигура 4.3: Изтриване на ключ на листов възел (30) от B дърво
Случай 2: Изтриването/Премахването на ключа се намира в нелистовия възел - Този случай е допълнително разделен на различни случаи:
1. Възелът, който не е Leaf/Internal, който е премахнат, се заменя с предшественик в ред, ако възелът Left child има повече от минималния брой ключове.
Нека визуализираме този случай, като използваме пример, в който ще изтрием ключ 33 от дървото B.
Фигура 4.4: Изтриване на ключ на листов възел (33) от B дърво
2. Възелът, който не е лист/вътрешен, който е премахнат, се заменя с наследник по ред, ако десният дъщерен възел има повече от минималния брой ключове.
Ако някое дете има минимален брой ключове, тогава ще обединим левия и десния дъщерни възли.
Нека визуализираме този случай, като изтрием ключ 30 от B дървото.
Фигура 4.5: Изтриване на ключ на листов възел (30) от B дърво
След сливането, ако родителският възел има по-малко от минималния брой ключове, може да се търсят братята и сестрите, както в Случай 1 .
1 милион в цифри
Случай 3: В следващия случай височината на дървото се свива. Ако целевият ключ се намира във вътрешен възел и премахването на ключа води до по-малко ключове във възела (което е по-малко от необходимия минимум), тогава потърсете поредния предшественик и поредния наследник. Ако и двете деца имат минимален брой ключове, тогава заемането не може да се случи. Това води до Случай 2(3) , т.е. обединяване на дъщерните възли.
Отново ще търсим брата или сестрата, за да вземем ключ назаем. Въпреки това, ако братът също се състои от минимален брой ключове, тогава ще обединим възела със брата заедно с родителския възел и ще подредим дъщерните възли според изискванията (възходящ ред).
Нека визуализираме този случай с помощта на пример, в който ще изтрием елемент от данни 10 от даденото B дърво.
Фигура 4.6: Изтриване на ключ на листов възел (10) от B дърво
Времевата сложност в горните примери варира в зависимост от местоположението, откъдето ключът трябва да бъде изтрит. По този начин времевата сложност за операцията по изтриване в B дърво е O(log?n) .
Заключението
В този урок научихме за B Tree и визуализирахме различните му операции с различни примери. Ние също така разбрахме някои основни свойства и правила на B дървото.