4634
правки
Binary split tree: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Binary split tree''' --- бинарное расщепляемое дерево. '''Binary split trees''' (BST's) are a data structure for storing static record…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Binary split tree''' | '''Binary split tree''' — ''[[бинарное расщепляемое дерево]].'' | ||
'''Binary split trees''' (BST's) are a data structure for storing static records with | '''Binary split trees''' (BST's) are a data structure for storing static records with | ||
skewed frequency distribution. Each node of the tree contains two | skewed frequency distribution. Each [[node]] of the [[tree]] contains two | ||
values, one of them | values, one of them being the key (records stored in this node | ||
are associated with this value), the other being a split value. The | are associated with this value), the other being a split value. The | ||
split value is used as a guide for further search in the tree if the | split value is used as a guide for further search in the tree if the | ||
key value is not equal to the search value. The reason to store two | key value is not equal to the search value. The reason to store two | ||
values is to ''decouple'' the conflicting functions of frequency | values is to ''decouple'' the conflicting functions of frequency | ||
ordering and subtree construction. | ordering and [[subtree]] construction. | ||
By separating the split value from the key value, we are allowed to | By separating the split value from the key value, we are allowed to | ||
store whatever key we want in the root without putting constraints on | store whatever key we want in the [[root]] without putting constraints on | ||
the structure of the subtree. The most reasonable choice of the root | the structure of the subtree. The most reasonable choice of the root | ||
is by selecting the most frequent key in the tree. | is by selecting the most frequent key in the tree. | ||
'''Binary split trees''' are also a special class of GBST's (''generalized binary split trees'') with the constraint of decreasing frequency. | '''Binary split trees''' are also a special class of GBST's (''[[generalized binary split tree|generalized binary split trees]]'') with the constraint of decreasing frequency. | ||
Note that the BST's and BT's do not contain each other. | Note that the BST's and BT's do not contain each other. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||