Раздел «Алгоритмы».BinarySearchTree:

Двоичное дерево поиска

Что такое двоичное дерево поиска?

Двоичное дерево поиска (binary search tree, BST) — это двоичное дерево, к каждой вершине которого приклепрены данные, а именно пара (ключ, значение). Ключ обычно является числом (целым или действительным), а в общем виде ключ — это элемент какого то множества, на котором определено отношение "больше" и "равно". В двоичном дереве поиска выполнено свойство:
значение ключа из левого поддерева вершины A <= значение ключа A < значение ключа любой вершины из правого поддерева.

Применение BST

Указанное свойство BST позволяет осществлять рекурсивый поиск в дереве элемента с нужным ключем. В дерево достаточно ветвистое (а точнее его высота не большая), этот поиск осуществляется достаточно быстро.

Введем обозначения

Search(root, key) = "найти вершину с ключем key в поддереве с корнем в вершине root".

1:function  Search(root, key)
2:    if(есть root->r  AND root->key > key)
3:        return Search(root->r);
4:    else if(есть root->l  AND root->key < key)
5:        return Search(root->l);
6:    else if(root->key == key)
7:        return root;
8:    else 
9:        return NULL;

Edit drawing 'btree' (requires a Java enabled browser)

За время O(h), где h - высота дерева, мы можем найти вершину с определенным ключем. Если элементы дерева добавляются в него случайно, то высота BST в среднем получается порядка O(log n), где n — число вершин.

Примеры кода, реализующего двоичное дерево

-- AntonPolyakov - 06 Apr 2004

Attachment sort Action Size Date Who Comment
btree.draw manage 5.0 K 08 Sep 2004 - 10:19 ArtemVoroztsov TWikiDraw? draw file
btree.gif manage 3.0 K 08 Sep 2004 - 10:19 ArtemVoroztsov TWikiDraw? GIF file