Книга: Программирование на языке Ruby

9.3.3. Использование двоичного дерева как справочной таблицы

9.3.3. Использование двоичного дерева как справочной таблицы

Пусть дерево уже отсортировано. Тогда оно может служить прекрасной справочной таблицей; например, для поиска в сбалансированном дереве, содержащем миллион узлов, понадобится не более 20 сравнений (глубина дерева равна логарифму числа узлов по основанию 2). Чтобы поиск был осмысленным, предположим, что в каждом узле хранится не какое-то одно значение, а ключ и ассоциированные с ним данные.

Почти всегда лучше использовать в качестве справочной таблицы хэш или даже таблицу во внешней базе данных. Но все равно приведем код:

class Tree
 # Предполагается, что определения взяты из предыдущего примера...
 def search(x)
  if self.data == x
   return self
  elsif x < self.data
   return left ? left.search(x) : nil
  else
   return right ? right.search(x) : nil
  end
 end
end
keys = [50, 20, 80, 10, 30, 70, 90, 5, 14,
        28, 41, 66, 75, 88, 96]
tree = Tree.new
keys.each {|x| tree.insert(x)}
s1 = tree.search(75)  # Возвращает ссылку на узел, содержащий 75...
s2 = tree.search(100) # Возвращает nil (не найдено).

Оглавление книги