Перавагі BST перад Hash Table


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка GE Healthcare Qualcomm
Двайковы пошук Двайковае дрэва гашыш тэорыя дрэва

Найбольш часта выкарыстоўваюцца аперацыі над любой структурай дадзеных - гэта ўстаўка, выдаленне і пошук. Табліца хэшаў здольная выконваць гэтыя тры аперацыі з сярэдняй часавай складанасцю O (1), адначасова балансуючы двайковы пошук Дрэвы возьмем O (log n) складанасць часу.

Спачатку здаецца, што хэш-табліцы лепш, чым самабалансаваныя BST ва ўсіх фарматах, бо складанасць аперацый у табліцы хэшаў менш, чым у BST. Але ёсць некаторыя ўмовы і патрабаванні, дзе мы аддаем перавагу BST перад хэш-табліцамі.

Перавагі BST перад Hash Table

Перавагі BST перад Hash Table

  1. Самабалансаваныя двайковыя дрэвы пошуку захоўваюць дадзеныя ў адсартаваным выглядзе, гэта значыць, мы можам атрымаць адсартаваныя дадзеныя, проста зрабіўшы парадак у парадку абход у БСТ. Але ў хэш-табліцах нам даводзіцца абыходзіць усе элементы і сартаваць іх пры дапамозе нейкай тэхнікі сартавання.
    Складанасць часу (хэш-табліца) = O (n часопіс (n))
    Складанасць часу (BST) = Аб (п)
  2. Знайдзіце максімальны вузел, мінімальны вузел, вузел, бліжэйшы да дадзенага значэння, альбо вузел, які проста перавышае дадзенае значэнне, і г. д. Усе аперацыі можна зрабіць за O (log n) час у дрэва двайковага пошуку, якое балансуе. Але ў выпадку з хэш-табліцамі нам трэба прайсці ўсе элементы, каб атрымаць адказ на згаданыя запыты.
    Складанасць часу (хэш-табліца) = Аб (п)
    Складанасць часу (BST) = O (часопіс n)
  3. Рэалізацыя наладжанага двайковага дрэва пошуку значна прасцей, чым рэалізацыя індывідуальнай табліцы хэшаў. Розныя мовы прадастаўляюць убудаваныя бібліятэкі для рэалізацыі індывідуальных хэш-табліц.
  4. Верхняя мяжа для ўсіх аперацый, такіх як ўстаўка, выдаленне, абнаўленне і пошук у дрэва двайковага пошуку, якое балансуецца, - O (часопіс n). Але ў выпадку з хэш-табліцамі верхняй мяжы няма. Аперацыі праходзяць пры сярэдняй складанасці O (1), але ў некаторых выпадках складанасць можа павялічыцца. Павелічэнне можа адбыцца дзякуючы таму, як бібліятэка ўкараняе хэш-табліцу. Асабліва, калі робіцца змяненне памеру хэш-табліцы, гэта вельмі дарагая аперацыя.

Такім чынам, і бінарныя дрэвы пошуку, і хэш-табліцы маюць свае перавагі ў розных сітуацыях. У залежнасці ад патрабаванняў трэба выбіраць паміж двайковым дрэвам пошуку і хэш-табліцай.

Даведка1    спасылка2