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 (не найдено).