Frequency-ordered binary search tree: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Frequency-ordered binary search tree''' --- частотно-упорядоченные бинарные деревья поиска. '''Frequency-ordered binar…») |
KVN (обсуждение | вклад) Нет описания правки |
||
| Строка 8: | Строка 8: | ||
It has been shown that the ratio between the access cost of a FOBT and | It has been shown that the ratio between the access cost of a FOBT and | ||
the optimal tree may be as high as <math>n/(4\log n)</math>. | the optimal tree may be as high as <math>n/(4\log n)</math>. | ||
[[Категория:Деревья]] | |||
[[Категория:Информационные деревья]] | |||
Текущая версия от 16:22, 23 ноября 2024
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].