Б ДРВО у структури података: Пример операције претраживања, уметања, брисања

Преглед садржаја:

Anonim

Шта је Б дрво?

Б Трее је самобалансирајућа структура података заснована на одређеном скупу правила за брже тражење, уметање и брисање података и меморијски ефикасан начин. Да би се то постигло, следе се следећа правила за стварање Б дрвета.

Б-Трее је посебна врста стабла у структури података. Ову методу је 1972. године први представио МцЦреигхт, а Баиер ју је назвао Хеигхт Баланцед м-ваи Сеарцх Трее. Помаже вам да сачувате сортиране и дозвољене разне операције попут уметања, претраживања и брисања података за мање времена.

У овом водичу за Б-Трее научићете:

  • Шта је Б дрво?
  • Зашто користити Б-Трее
  • Историја дрвета Б
  • Операција претраживања
  • Инсерт Оператион
  • Делете Оператион

Правила за Б-дрво

Овде су важна правила за стварање Б_Трее

  • Сви листови ће бити створени на истом нивоу.
  • Б-Трее се одређује бројем степена, који се такође назива „редоследом“ (који одређује спољни актер, попут програмера), који се назива 
    m
    па надаље. Вредност 
    m
    зависи од величине блока на диску на коме се превасходно налазе подаци.
  • Лево подстабло чвора имаће мање вредности од десне стране подстабла. То значи да су чворови такође сортирани у растућем редоследу с лева на десно.
  • Максималан број подређених чворова, који може садржати основни чвор, као и његови подређени чворови, израчунава се по овој формули: 
    m - 1
    На пример: 
    m = 4max keys: 4 - 1 = 3

  • Сваки чвор, осим роот-а, мора садржавати најмање кључева од 
    [m/2]-1
    На пример: 
    m = 4min keys: 4/2-1 = 1
  • Максималан број подређених чворова које чвор може имати једнак је његовом степену, тј 
    m
  • Минимално подређених делова које чвор може имати је половина редоследа, што је м / 2 (узима се горња вредност).
  • Сви кључеви у чвору сортирани су у порасту.

Зашто користити Б-Трее

Ево разлога за употребу Б-Трее-а

  • Смањује број читања извршених на диску
  • Б Дрвеће се лако може оптимизовати да прилагоди његову величину (то је број подређених чворова) у складу са величином диска
  • То је посебно дизајнирана техника за руковање гломазном количином података.
  • То је користан алгоритам за базе података и системе датотека.
  • Добар избор да се одлучите за читање и писање великих блокова података

Историја дрвета Б

  • Подаци се на диску чувају у блоковима, ти подаци, када се унесу у главну меморију (или РАМ), називају се структура података.
  • У случају огромних података, претрага једног записа на диску захтева читање целог диска; ово повећава потрошњу времена и главне меморије због велике фреквенције приступа диску и величине података.
  • Да би се ово превазишло, креирају се индексне табеле које чувају референцу записа на основу блокова у којима се налазе. То драстично смањује време и потрошњу меморије.
  • Будући да имамо огромне податке, можемо да креирамо индексне табеле на више нивоа.
  • Индекс на више нивоа може се дизајнирати коришћењем Б Трее за одржавање сортираних података на самобалансирајући начин.

Операција претраживања

Операција претраживања је најједноставнија операција на Б дрвету.

Примењује се следећи алгоритам:

  • Нека кључ (вредност) претражује „к“.
  • Почните да претражујете од корена и рекурзивно прелазите доле.
  • Ако је к мања од коренске вредности, претражите лево подстабло, ако је к већа од коренске вредности, претражите десно подстабло.
  • Ако чвор има пронађено к, једноставно га вратите.
  • Ако к није пронађен у чвору, пређите до детета помоћу већег кључа.
  • Ако к није пронађен у стаблу, вратит ћемо НУЛЛ.

Инсерт Оператион

Будући да је Б Трее самобалансирајуће стабло, не можете на силу уметнути кључ у било који чвор.

Примењује се следећи алгоритам:

  • Покрените операцију претраживања и пронађите одговарајуће место уметања.
  • Уметните нови кључ на одговарајуће место, али ако чвор већ има максималан број кључева:
  • Чвор ће се заједно са ново убаченим кључем одвојити од средњег елемента.
  • Средњи елемент постаће родитељ за друга два подређена чвора.
  • Чворови морају преуређивати кључеве у растућем редоследу.

САВЕТ

Следеће није тачно у вези са алгоритмом уметања:

Пошто је чвор пун, зато ће се поделити, а затим ће се уметнути нова вредност

У горњем примеру:

  • Потражите кључ на одговарајућем месту у чвору
  • Уметните кључ у циљни чвор и проверите да ли постоје правила
  • Да ли чвор након уметања има више него једнак минималном броју кључева, што је 1? У овом случају, да, има. Проверите следеће правило.
  • Да ли чвор након уметања има више од максималног броја кључева, што је 3? У овом случају не, није. То значи да дрво Б не крши ниједно правило и да је уметање завршено.

У горњем примеру:

  • Чвор је достигао максималан број кључева
  • Чвор ће се подијелити, а средњи кључ ће постати коријенски чвор преостала два чвора.
  • У случају парног броја тастера, средњи чвор ће се одабрати левом или десном пристрасношћу.

У горњем примеру:

  • Чвор има мање од максималних кључева
  • 1 се убацује поред 3, али се крши правило растућег реда
  • Да би се ово поправило, кључеви су сортирани

Слично томе, 13 и 2 могу се лако уметнути у чвор јер испуњавају правило кључева мање од максимума за чворове.

У горњем примеру:

  • Чвор има кључеве једнаке максималним кључевима.
  • Кључ је уметнут у циљни чвор, али крши правило макс. Кључева.
  • Циљни чвор је подијељен, а средњи кључ лијеве пристраности сада је родитељ нових подређених чворова.
  • Нови чворови су распоређени у растућем редоследу.

Слично томе, на основу горњих правила и случајева, остале вредности се могу лако уметнути у дрво Б.

Делете Оператион

Операција брисања има више правила од операција уметања и претраживања.

Примењује се следећи алгоритам:

  • Покрените операцију претраживања и пронађите циљни кључ у чворовима
  • Примењена су три услова на основу локације циљног кључа, као што је објашњено у следећим одељцима

Ако је циљни кључ у чвору листа

  • Циљ је у чвору листа, више од мин кључева.
    • Брисањем овога неће се прекршити својство дрвета Б
  • Циљ је у чвору листа, има мин чворова кључева
    • Ако ово избришете, нарушиће се својство дрвета Б
    • Циљни чвор може позајмити кључ од непосредног левог чвора или непосредног десног чвора (брата или сестре)
    • Брат или сестра ће рећи да ако има више од минималног броја кључева
    • Кључ ће бити позајмљен од надређеног чвора, максимална вредност ће се пренети надређеном, максимална вредност надређеног чвора ће се пренети у циљни чвор и уклонити циљну вредност
  • Циљ је у чвору листа, али ниједна браћа и сестре немају више од минималног броја кључева
    • Потражите кључ
    • Споји се са браћом и сестрама и минимумом родитељских чворова
    • Укупан број кључева сада ће бити већи од мин
    • Циљни кључ ће бити замењен минимумом надређеног чвора

Ако је циљни кључ у унутрашњем чвору

  • Или одаберите, претходника по реду или наследника по реду
  • У случају претходника по редоследу, биће изабран максималан тастер са његовог левог подстабла
  • У случају наследника по реду, биће изабран минимални кључ из његовог десног подстабла
  • Ако претходник циљаног кључа по редоследу има више од мин кључева, само тада може циљни кључ заменити максимумом претходника по редоследу
  • Ако претходник циљаног кључа по редоследу нема више од мин кључева, потражите минимални кључ наследника по реду.
  • Ако претходник и наследник циљаног кључа имају мање од мин кључева, тада спојите претходника и наследника.

Ако је циљни кључ у коренском чвору

  • Замените максималним елементом претходног подстабла по реду
  • Ако након брисања циљ има мање од мин кључева, циљни чвор ће позајмити максималну вредност од свог брата или сестре преко родитеља сестре.
  • Циљ ће узети максималну вредност родитеља, али са чворовима максималне вредности брата и сестре.

Хајде сада да разумемо операцију брисања на примеру.

Горњи дијаграм приказује различите случајеве операције брисања у Б-стаблу. Ово Б-стабло је реда 5, што значи да је најмањи број подређених чворова који било који чвор може имати 3, а максималан број подређених чворова било који чвор може бити 5. Док је најмањи и максималан број кључева било којег чвора могу имати 2, односно 4.

У горњем примеру:

  • Циљни чвор има циљни кључ за брисање
  • Циљни чвор има кључеве више од минималних кључева
  • Једноставно избришите кључ

У горњем примеру:

  • Циљни чвор има кључеве једнаке минималним кључевима, па га не можете директно избрисати јер ће прекршити услове

Следећи дијаграм објашњава како да избришете овај кључ:

  • Циљни чвор ће позајмити кључ од непосредног брата или сестре, у овом случају, претходника по редоследу (леви брат или сестра) јер нема ниједног наследника по редоследу (десни брат)
  • Максимална вредност претходника инордер биће пренета на родитеља, а родитељ ће пренети максималну вредност на циљни чвор (погледајте дијаграм испод)

Следећи пример илуструје како избрисати кључ којем је потребна вредност из наследника по реду.

  • Циљни чвор ће позајмити кључ од непосредног брата или сестре, у овом случају, наследника по реду (десни брат), јер његов претходник по редоследу (леви брат или сестра) има кључеве једнаке минималним кључевима.
  • Минимална вредност наследника по редоследу биће пренета на родитеља, а родитељ ће пренети максималну вредност на циљни чвор.

У примеру испод, циљни чвор нема брата или сестру који могу дати свој кључ циљном чвору. Због тога је потребно спајање.

Погледајте поступак брисања таквог кључа:

  • Споји циљни чвор са било којим од његових непосредних браће и сестара заједно са родитељским кључем
    • Одабран је кључ надређеног чвора који се брати између два чвора која се спајају
  • Избришите циљни кључ из спојеног чвора

Избришите псеудо код операције

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}}

Излаз :

Највећи елемент је избрисан са Б-дрвета.

Резиме:

  • Б Трее је самобалансирајућа структура података за бољу претрагу, уметање и брисање података са диска.
  • Б Дрво је регулисано наведеним степеном
  • Б Кључеви и чворови стабла распоређени су у растућем редоследу.
  • Операција претраживања Б дрвета је најједноставнија, која увек започиње од корена и започиње проверу да ли је циљни кључ већи или мањи од вредности чвора.
  • Операција уметања Б стабла је прилично детаљна, која прво проналази одговарајући положај уметања за циљни кључ, убацује га, процењује ваљаност Б стабла у односу на различите случајеве, а затим реструктурира чворове Б стабла у складу с тим.
  • Операција брисања Б дрвета прво тражи циљни кључ који треба избрисати, брише га, процењује ваљаност на основу неколико случајева попут минималног и максималног кључа циљног чвора, браће и сестара и родитеља.