Optimal Binary Search Trees: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 11: Line 11:


=Overview=
=Overview=
A [[Binary_Search_Trees#Balanced_Binary_Search_Trees|balanced binary search]] tree exposes its nodes via at most log n node traversals. However, if some of the search terms are more accessed than others, and we know a priori the relative access frequency, a balanced search tree is not optimal. Instead, a tree that keeps the most frequently accessed nodes higher up in the tree offers better performance overall.

Revision as of 21:06, 2 November 2021

External

Internal

Overview

A balanced binary search tree exposes its nodes via at most log n node traversals. However, if some of the search terms are more accessed than others, and we know a priori the relative access frequency, a balanced search tree is not optimal. Instead, a tree that keeps the most frequently accessed nodes higher up in the tree offers better performance overall.