Binary split tree

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.