 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Дихотомические деревья (деревья поиска)
|
|
Бинарные деревья часто используются для представления множества объектов, среди которых идет поиск по уникальному значению некоторого атрибута, называемого ключом. При этом на множестве объектов определенно особое отношение порядка - дихотомия, заключающееся в поэтапном разбиении множества информационных полей объектов на два непересекающихся подмножества. Дихотомическим деревом (деревом поиска) называется бинарное дерево, организованное так, что для каждого узла, имеющего ключ Т, справедливо утверждение о том, что в его левом поддереве содержатся узлы с ключами, меньшими T, а в его правом поддереве содержатся узлы с ключами, большими T.
Описание элемента хранения узла дихотомического дерева:
| Type | |
| PDtree = ^ Dtree; | { тип – указатель на узел дихотомического дерева } |
| Dtree = record | { тип – элемент хранения узла дихотомического дерева} |
| key: word; | { поле ключа } |
| info: char; | { информационное поле } |
| left, right: PDtree | { ссылки на поддеревья } |
| end; | |
| Var Root: PDtree; | { указатель на корень дихотомического дерева } |
Пример дихотомических деревьев приведен на рис. 70:
 |  |
Дата публикования: 2014-11-26; Прочитано: 1822 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
