Двоичные деревья поиска¶

Мы уже видели два различных способа получить коллекцию из пар ключ-значение. Напомним, что её воплощает абстрактный тип данных map. Мы обсуждали две его реализации: с помощью списка и хэш-таблицы. В этом разделе мы изучим двоичные деревья поиска, как ещё один способ отображать ключ на значение. В этом случае нам не интересно точное расположение элементов в дереве. Мы заинтересованы в использовании структуры двоичного дерева для эффективного поиска.