Деј-Стоут-Варен алгоритам
Деј-Стоут-Варен (ДСВ) алгоритам, је метода за ефикасно балансирање бинарне претраге стабла - тј., смањивање њихове висине на О(логн) чворова, где је н укупан број чворова. За разлику од самобалансирајућег бинарног стабла, ово не ради постепено после сваке операције, већ периодично, тако да цена мозе бити амортизована преко више операција. Алгоритам је дизајнирао Квентин Ф. Стоут и Бете Варен 1986 у раду "Трее Ребаланцинг ин Оптимал Тиме анд Спаце", базиран на раду Колина Даи из 1976.[1][2]
Алгоритам захтева линеарно време (О(н)) и у месту је. Оригинални алгоритам се генерише као компактно стабло: сви нивои стабла су потпуно пуни осим можда последњих (најнижих). Стоут/Варен модификација генерише потпуно бинарно стабло, наиме оно у коме су најниже гране попуњене с лева на десно. Ово је корисна трансформација за извођење ако се зна да неце бити висе уноса у стабло.[3]
Чланак који је написао Тимоти Ј. Ролфе 2002. је скоро вратио пажњу на ДСВ алгоритам после дуго времена; именовање је из дела наслова "6.7.1: ДСВ Алгоритам" у делу Адама Дроздека "Дата Структуре и Алгоритми у C++". Ролфе цитира две главне предности: "у околностима које генерису цело бинарно стабло на почетку обраде, праћено проналажењем приступа за остатак обраде" и "педагогшки у процесу дата структуре где један напредује из бинарне претраге стабла у самоподешавајуће стабло, пошто даје прво излагање за ротације унутар бинарне претраге стабла".[4]
Референце
[уреди | уреди извор]- ^ Стоут, Qуентин Ф.; Wаррен, Бетте L. (1986). „Трее ребаланцинг ин оптимал спаце анд тиме” (ПДФ). ЦАЦМ. 29 (9): 902—908. дои:10.1145/6592.6599.
- ^ Даy, А. Цолин (1976). „Баланцинг а Бинарy Трее”. Цомпут. Ј. 19 (4): 360—361. дои:10.1093/цомјнл/19.4.360
.
- ^ Ролфе, Тимотхy Ј. (2002). „Оне-Тиме Бинарy Сеарцх Трее Баланцинг: Тхе Даy/Стоут/Wаррен (ДСW) Алгоритхм”. СИГЦСЕ Буллетин. АЦМ СИГЦСЕ. 34 (4): 85—88. дои:10.1145/820127.820173. Архивирано из оригинала 13. 12. 2012. г. Приступљено 06. 02. 2017.
- ^ Дроздек, Адам (1996). Дата Струцтурес анд Алгоритхмс ин C++. ПWС Публисхинг Цо. стр. 173–175. ИСБН 0-534-94974-6.
