Frequency-ordered binary search tree

Frequency-ordered binary search tree --- частотно-упорядоченные бинарные деревья поиска.

Frequency-ordered binary search tree (or FOBT) is a binary search tree that satisfies the condition that the root of a subtree must have the highest frequency. In other words, the frequencies of nodes along any path (from root top leaf) must be decreasing (or not-increasing). It has been shown that the ratio between the access cost of a FOBT and the optimal tree may be as high as [math]\displaystyle{ n/(4\log n) }[/math].