B ДЪРВО в Структура на данни: Пример за търсене, вмъкване, изтриване

Съдържание:

Anonim

Какво е B дърво?

B Tree е самобалансираща се структура от данни, базирана на специфичен набор от правила за търсене, вмъкване и изтриване на данните по-бързо и ефективно с памет. За да се постигне това, се спазват следните правила за създаване на B дърво.

B-Tree е специален вид дърво в структурата на данните. През 1972 г. този метод беше представен за пръв път от McCreight и Bayer го нарече Height Balanced m-way Tree Tree. Той ви помага да запазите сортирани данни и разрешени различни операции като вмъкване, търсене и изтриване за по-малко време.

В този урок за B-Tree ще научите:

  • Какво е B дърво?
  • Защо да използваме B-Tree
  • История на B Tree
  • Операция за търсене
  • Вмъкване на операция
  • Изтриване на операцията

Правила за B-Tree

Тук има важни правила за създаване на B_Tree

  • Всички листа ще бъдат създадени на едно и също ниво.
  • B-Tree се определя от определен брой степени, които също се наричат ​​"ред" (посочени от външен актьор, като програмист), наричан 
    m
    нататък. Стойността на 
    m
    зависи от размера на блока на диска, на който се намират предимно данните.
  • Лявото поддърво на възела ще има по-малки стойности от дясната страна на поддървото. Това означава, че възлите също са сортирани във възходящ ред отляво надясно.
  • Максималният брой дъщерни възли, коренни възел, както и неговите дъщерни възли, които могат да съдържат, се изчисляват по тази формула: 
    m - 1
    Например: 
    m = 4max keys: 4 - 1 = 3

  • Всеки възел, с изключение на root, трябва да съдържа минимум ключове от 
    [m/2]-1
    Например: 
    m = 4min keys: 4/2-1 = 1
  • Максималният брой дъщерни възли, които един възел може да има, е равен на неговата степен, което е 
    m
  • Минималният брой деца, които един възел може да има, е половината от поръчката, което е m / 2 (взема се таванната стойност).
  • Всички ключове в възел са сортирани в нарастващ ред.

Защо да използваме B-Tree

Ето причините за използването на B-Tree

  • Намалява броя на четенията, направени на диска
  • B Дърветата могат лесно да бъдат оптимизирани, за да коригират размера му (т.е. броя на дъщерните възли) според размера на диска
  • Това е специално разработена техника за обработка на обемно количество данни.
  • Това е полезен алгоритъм за бази данни и файлови системи.
  • Добър избор да изберете, когато става въпрос за четене и запис на големи блокове данни

История на B Tree

  • Данните се съхраняват на диска на блокове, тези данни, когато се внасят в основната памет (или RAM), се наричат ​​структура на данните.
  • В случай на огромни данни, търсенето на един запис на диска изисква четене на целия диск; това увеличава консумацията на време и основна памет поради високата честота на достъп до диска и размера на данните.
  • За да се преодолее това, се създават индексни таблици, които запазват референцията на записите на записите въз основа на блоковете, в които се намират. Това драстично намалява времето и консумацията на памет.
  • Тъй като разполагаме с огромни данни, можем да създаваме таблици с индекси на много нива.
  • Индексът на няколко нива може да бъде проектиран чрез използване на B Tree за поддържане на сортирането на данните по начин на самобалансиране.

Операция за търсене

Операцията за търсене е най-простата операция на B Tree.

Прилага се следният алгоритъм:

  • Нека ключът (стойността) да бъде търсен с "k".
  • Започнете да търсите от корена и рекурсивно преминавайте надолу.
  • Ако k е по-малко от основната стойност, потърсете лявото поддърво, ако k е по-голямо от основната стойност, потърсете дясното поддърво.
  • Ако възелът има намереното k, просто върнете възела.
  • Ако k не е намерен във възела, преминете надолу към детето с по-голям ключ.
  • Ако k не е намерен в дървото, връщаме NULL.

Вмъкване на операция

Тъй като B Tree е самобалансиращо се дърво, не можете да принудите да вмъкнете ключ в който и да е възел.

Прилага се следният алгоритъм:

  • Изпълнете операцията за търсене и намерете подходящото място за вмъкване.
  • Поставете новия ключ на правилното място, но ако възелът вече има максимален брой ключове:
  • Възелът, заедно с нововмъкнат ключ, ще се раздели от средния елемент.
  • Средният елемент ще се превърне в родител за останалите два дъщерни възела.
  • Възлите трябва да пренареждат ключовете във възходящ ред.

БАКШИШ

Следното не е вярно за алгоритъма за вмъкване:

Тъй като възелът е пълен, следователно той ще се раздели и след това ще се вмъкне нова стойност

В горния пример:

  • Потърсете ключа в съответната позиция в възела
  • Поставете ключа в целевия възел и проверете за правила
  • След вмъкването възелът има ли повече от равно на минимален брой ключове, което е 1? В този случай да, така е. Проверете следващото правило.
  • След вмъкването възелът има ли повече от максимален брой ключове, което е 3? В този случай не, не е така. Това означава, че дървото B не нарушава никакви правила и вмъкването е завършено.

В горния пример:

  • Възелът е достигнал максималния брой ключове
  • Възелът ще се раздели и средният ключ ще се превърне в основен възел на останалите два възела.
  • В случай на четен брой ключове, средният възел ще бъде избран чрез ляво или дясно пристрастие.

В горния пример:

  • Възелът има по-малко от максимални ключове
  • 1 се вмъква до 3, но правилото за възходящ ред е нарушено
  • За да се поправи това, ключовете се сортират

По подобен начин 13 и 2 могат лесно да бъдат вмъкнати във възела, тъй като изпълняват правилото за ключовете по-малко от максималното за възлите.

В горния пример:

  • Възелът има ключове, равни на максимални ключове.
  • Ключът се вмъква в целевия възел, но нарушава правилото за максимални ключове.
  • Целевият възел е разделен и средният ключ от ляво пристрастие вече е родител на новите дъщерни възли.
  • Новите възли са подредени във възходящ ред.

По същия начин, въз основа на горните правила и случаи, останалите стойности могат лесно да бъдат вмъкнати в дървото B.

Изтриване на операцията

Операцията за изтриване има повече правила от операциите за вмъкване и търсене.

Прилага се следният алгоритъм:

  • Изпълнете операцията за търсене и намерете целевия ключ във възлите
  • Приложени са три условия въз основа на местоположението на целевия ключ, както е обяснено в следващите раздели

Ако целевият ключ е в листовия възел

  • Целта е в листовия възел, повече от мин ключове.
    • Изтриването на това няма да наруши свойството на B Tree
  • Целта е в листовия възел, има минимални ключови възли
    • Изтриването на това ще наруши свойството на B Tree
    • Целевият възел може да заеме ключ от непосредствен ляв възел или непосредствен десен възел (брат или сестра)
    • Братът ще каже „ да“, ако има повече от минималния брой ключове
    • Ключът ще бъде заимстван от родителския възел, максималната стойност ще бъде прехвърлена към родител, максималната стойност на родителския възел ще бъде прехвърлена към целевия възел и ще премахне целевата стойност
  • Целта е в листния възел, но никой от братята и сестрите няма повече от минимален брой ключове
    • Търсене на ключ
    • Обединяване с братя и сестри и минимум родителски възли
    • Общият брой на ключовете вече ще бъде повече от мин
    • Целевият ключ ще бъде заменен с минимум на родителски възел

Ако целевият ключ е във вътрешен възел

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

Ако целевият ключ е в корен възел

  • Заменете с максималния елемент на поддървото на предшественика по ред
  • Ако след изтриването целта има по-малко от мин ключове, целевият възел ще заеме максимална стойност от своя брат или сестра чрез родителя на сестра.
  • Максималната стойност на родителя ще бъде взета от цел, но с възлите на максималната стойност на брат или сестра.

Сега, нека разберем операцията за изтриване с пример.

Горната диаграма показва различни случаи на операция за изтриване в B-Tree. Това B-дърво е от порядък 5, което означава, че минималният брой дъщерни възли, които всеки възел може да има, е 3, а максималният брой дъщерни възли, който всеки възел може да има, е 5. Докато минималният и максималният брой ключове на всеки възел може да има съответно 2 и 4.

В горния пример:

  • Целевият възел има целевия ключ за изтриване
  • Целевият възел има ключове повече от минималните ключове
  • Просто изтрийте ключа

В горния пример:

  • Целевият възел има ключове, равни на минимални ключове, така че не може да го изтрие директно, тъй като това ще наруши условията

Следващата диаграма обяснява как да изтриете този ключ:

  • Целевият възел ще заеме ключ от незабавно събрат, в този случай предшественик по ред (ляв брат или сестра), тъй като няма наследник по ред (десен брат)
  • Максималната стойност на предшественика inorder ще бъде прехвърлена на родителя и родителят ще прехвърли максималната стойност на целевия възел (вижте диаграмата по-долу)

Следващият пример илюстрира как да изтриете ключ, който се нуждае от стойност, от неговия наследник по ред.

  • Целевият възел ще заеме ключ от незабавно събрат, в този случай наследник по ред (десен брат), тъй като предшественикът му по ред (ляв брат) има ключове, равни на минимални ключове.
  • Минималната стойност на наследника по ред ще бъде прехвърлена на родителя, а родителят ще прехвърли максималната стойност на целевия възел.

В примера по-долу целевият възел няма брат или сестра, който може да даде своя ключ на целевия възел. Следователно е необходимо обединяване.

Вижте процедурата за изтриване на такъв ключ:

  • Обединете целевия възел с някое от неговите непосредствени братя и сестри заедно с родителския ключ
    • Избран е ключът от родителския възел, който се свързва между двата обединяващи се възела
  • Изтрийте целевия ключ от обединения възел

Изтриване на операция Псевдо код

private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}

Изход :

Най-големият елемент е изтрит от B-Tree.

Резюме:

  • B Tree е самобалансираща се структура от данни за по-добро търсене, вмъкване и изтриване на данни от диска.
  • B Дървото се регулира от определената степен
  • B Ключовете и възлите на дърветата са подредени във възходящ ред.
  • Операцията за търсене на B Tree е най-простата, която винаги започва от корена и започва да проверява дали целевият ключ е по-голям или по-малък от стойността на възела.
  • Операцията за вмъкване на B Tree е доста подробна, която първо намира подходяща позиция на вмъкване за целевия ключ, вмъква го, оценява валидността на B Tree спрямо различни случаи и след това преструктурира възлите на B Tree съответно.
  • Операцията за изтриване на B Tree първо търси целевия ключ, който трябва да бъде изтрит, изтрива го, оценява валидността въз основа на няколко случая като минимален и максимален ключове на целевия възел, братя и сестри и родител.