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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''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.

Текущая версия от 16:31, 23 октября 2018

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.