Бинарно стебло за пребарување

Бинарно стебло за пребарување
	Бинарно стебло за пребарување со големина 9 и длабочина 3, со бројот 8 како корен.
Општи информации
Тип	стебло
Пронајдена во	1960
Пронаоѓач	П. Ф. Виндли, А. Д. Бут, А. Џ. Т. Колин и Т. Н. Хибард
Операција	Просек
Временска сложеност (O-нотација)
Операција	Просек
Пребарување	Θ(log n)
Вметнување	Θ(log n)
Бришење	Θ(log n)
Просторна сложеност
Простор	Θ(n)

Бинарно стебло за пребарување (англиски: binary search tree, BST) — бинарно стебло за кое се исполнети следниве дополнителни услови (својства на стебло за пребарување):

двете потстебла — левото и десното — се бинарни стебла за пребарување;
кај сите јазли на левото потстебло на кој било јазол X, вредностите на клучот на податоците се помали или еднакви на вредноста на клучот на самиот јазол X;
кај сите јазли на десното потстебло на кој било јазол X, вредностите на клучот на податоците се поголеми од вредноста на клучот на самиот јазол X.

Очигледно, податоците во секој јазол мора да поседуваат клучеви врз кои е определена операцијата за споредба помало или еднакво.

Како по правило, информацијата што ја претставува секој јазол е запис, а не едно податочно поле. Како и да е, ова се однесува на имплементацијата, а не на природата на бинарното стебло за пребарување.^[1]

Определба за имплементација

За потребите на имплементацијата, бинарното стебло за пребарување може да се определи вака:

Бинарното стебло се состои од јазли (темиња) — записи од видот (data, left, right), каде што data се некои податоци поврзани со јазолот, а left и right се врски кон јазлите што се деца на тој јазол — соодветно левиот и десниот син. За оптимизација на алгоритмите, конкретните имплементации претпоставуваат и определување на полето parent во секој јазол (освен кај коренот) — врска кон родителскиот елемент.
Податоците (data) поседуваат клуч (key) врз кој е определена операцијата за споредба „помало“. Во конкретни имплементации, тоа може да биде пар (key, value) — (клуч, вредност), или врска кон таков пар, или едноставна определба на операцијата за споредба на соодветната податочна структура.
За кој било јазол X се исполнети својствата на стеблото за пребарување: ${\text{key}}[{\text{left}}[X]]\leq {\text{key}}[X]<{\text{key}}[{\text{right}}[X]]$ , односно клучевите на податоците на родителскиот јазол се нестрого поголеми од клучевите на левиот син и помали од клучевите на десниот.

Бинарното стебло за пребарување не треба да се меша со бинарен куп, кој е изграден според поинакви правила.

Предности и примена

Главната предност на бинарното стебло за пребарување пред другите структури на податоци е можната висока ефикасност во имплементацијата на алгоритмите за пребарување и сортирање засновани на него.

Бинарното стебло за пребарување се применува за изградба на поапстрактни структури, како што се:

Множества
Мултимножество
Асоцијативна низа (асоцијативни масиви)

Основни операции во бинарно стебло за пребарување

Основниот интерфејс на бинарното стебло за пребарување се состои од три операции:

FIND(K) — пребарување на јазол во кој се чува парот (key, value) со key = K.
INSERT(K, V) — додавање во стеблото на парот (key, value) = (K, V).
REMOVE(K) — бришење на јазолот во кој се чува парот (key, value) со key = K.

Овој апстрактен интерфејс е општ случај за интерфејси преземени од применети задачи како:

Телефонски именик — складиште на записи (име на човек, негов телефон) со операции за пребарување и бришење записи според името и операција за додавање нов запис.
Domain Name Server — складиште на парови (доменско име, IP-адреса) со операции за измена и пребарување.
Namespace — складиште на имиња на променливи со нивните вредности кај преведувачите на програмски јазици.

Во суштина, бинарното стебло за пребарување е структура на податоци способна да чува табела со парови (key, value) и поддржува три операции: FIND, INSERT и REMOVE.

Покрај тоа, интерфејсот вклучува уште три операции за поминување (обиколка) на јазлите: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Првата овозможува обиколка во поредок на нерастечки (растечки) редослед на клучевите.

Наводи

↑ Culberson, J.; Munro, J. I. (1 January 1989). „Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations“. The Computer Journal. 32 (1): 68–69. doi:10.1093/comjnl/32.1.68.

Надворешни врски

Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. (PDF; 1675 kB) 2004.
Binary Search Tree Visualization

[computer_journal89-1] Culberson, J.; Munro, J. I. (1 January 1989). „Explaining the Behaviour of Binary Search Trees Under Prolonged Updates: A Model and Simulations“. The Computer Journal. 32 (1): 68–69. doi:10.1093/comjnl/32.1.68.

[1]