Препоръчано, 2022

Избор На Редактора

Разлика между B-дърво и двоично дърво

B-tree и Binary tree са видовете нелинейна структура на данните. Въпреки че термините изглеждат сходни, но са различни във всички аспекти. Двоично дърво се използва, когато записите или данните се съхраняват в RAM вместо на диска, тъй като скоростта на достъп до RAM е много по-висока от тази на диска. От друга страна, B-дървото се използва, когато данните се съхраняват в диска и намалява времето за достъп, като намалява височината на дървото и увеличава клоновете в възела.

Друга разлика между B-дървото и двоичното дърво е, че B-дървото трябва да има всички негови детски възли на едно и също ниво, докато двоичното дърво няма такова ограничение. Двоичното дърво може да има максимум 2 поддерева или възли, докато в B-дървото може да има M no от поддерев или възли, където M е редът на B-дървото.

Сравнителна таблица

Основа за сравнение
B-дърво
Двоично дърво
Съществено ограничениеВъзел може да има най-много M брой дъщерни възли (където M е реда на дървото).Един възел може да има максимум 2 броя под-дървета.
Използва се
Използва се, когато данните се съхраняват на диск.Използва се, когато записите и данните се съхраняват в RAM.
Височина на дървотоlog M N (където m е реда на дървото M-way)log 2 N
ПриложениеСтруктурата на данните за индексиране на кодове в много СУБД.Оптимизиране на код, кодиране на Huffman и др.

Дефиниция на В-дърво

B-дървото е балансираното дърво на M-way и е известно също като балансирано сортирано дърво. Той е подобен на двоичното дърво за търсене, където възлите са организирани на базата на прехвърлянето. Пространствената сложност на B-дървото е O (n). Времевата сложност на вмъкване и изтриване е O (log n).

Има определени условия, които трябва да са верни за B-дърво:

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

Свойства на B-дърво от ред M

  • Всеки възел може да има максимум М брой деца и минимален брой М / 2 деца или всяко число от 2 до максимум.
  • Всеки възел има по един ключ по-малък от децата с максимални M-1 ключове.
  • Подреждането на ключовете е в някакъв специфичен ред в рамките на възлите. Всички ключове в поддървото, което се намира в лявата част на ключа, са предшественици на ключа, и това, което присъства в дясната част на ключа, се наричат ​​наследници.
  • По време на вмъкването на пълен възел, дървото се разделя на две части, а ключът със средна стойност се вмъква в родителския възел.
  • Операцията по сливане се извършва, когато възлите са изтрити.

Дефиниция на двоичното дърво

Двоичното дърво е дървовидна структура, която може да има най-много две указатели за своите детски възли. Това означава, че най-високата степен, която един възел може да има, е 2 и може да има и нула или един градус възел.

Има някои варианти на двоично дърво, като строго двоично дърво, пълно двоично дърво, разширено двоично дърво и т.н.

  • Строго двоичното дърво е дърво, където всеки не-терминален възел трябва да има ляво поддърво и дясно поддърво.
  • Дърво се нарича Пълно двоично дърво, когато отговаря на условието да има 2 i възли на всяко ниво, където i е нивото.
  • Нишковиден двоичен е двоично дърво, което се състои от 0 или 0 от възли.

Техники на траверса

Преминаването на дървото е една от най-честите операции, извършвани в дървовидна структура на данни, в която всеки възел е посещаван точно веднъж по систематичен начин.

  • Inorder- В това пресичане на дървото левият поддърво се посещава рекурсивно, след което се разглежда коренния възел и в последното дясно поддърво се посещава.
  • Preorer- В това пресичане на дървото коренният възел се посещава първо след това вляво поддърво и най-накрая дясно поддърво.
  • Постери - Тази техника посещава ляво поддърво, след това дясно поддърво и най-накрая корен.

Ключови разлики между B-дърво и двоично дърво

  1. В B-tree максималният брой на детските възли, които може да има не-терминален възел, е M, където M е редът на B-дървото. От друга страна, двоичното дърво може да има най-много две поддерева или детски възли.
  2. B-tree се използва, когато данните се съхраняват на диск, докато двоичното дърво се използва, когато данните се съхраняват в бърза памет като RAM.
  3. Друга област на приложение за B-tree е структурата на данните за индексиране на кодове в СУБД, за разлика от това бинарното дърво се използва в оптимизацията на кода, кодирането на huffman и др.
  4. Максималната височина на B-дървото е log M N (M е реда на дървото). Максималната височина на двоичното дърво е log 2 N (N е броят на възлите, а базата е 2, защото е за двоичен).

заключение

B-дървото се използва над двоично и двоично дърво за търсене, като основната причина за това е йерархията на паметта, където CPU е свързан с кеш с канали с висока честотна лента, докато CPU е свързан към диск чрез канал с ниска честотна лента. Двоично дърво се използва, когато записите се съхраняват в RAM (малки и бързи) и B-дървото се използва, когато записите се съхраняват на диск (голям и бавен). Така че използването на B-tree вместо Binary tree значително намалява времето за достъп поради висок коефициент на разклоняване и намалена височина на дървото.

Top