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. | |||
Текущая версия от 11:14, 8 февраля 2012
Binary split tree — бинарное расщепляемое дерево.
Binary split trees (BST's) are a data structure for storing static records with skewed frequency distribution. Each node of the tree contains two values, one of them being the key (records stored in this node 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 key value is not equal to the search value. The reason to store two values is to decouple the conflicting functions of frequency ordering and subtree construction.
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 the structure of the subtree. The most reasonable choice of the root 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.
Note that the BST's and BT's do not contain each other.
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.