Binary split tree: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Binary split tree''' --- бинарное расщепляемое дерево. '''Binary split trees''' (BST's) are a data structure for storing static record…»)
 
Нет описания правки
 
Строка 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 being being the key (records stored in this node
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.

Навигация