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

We use cookies. Read the Privacy and Cookie Policy

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

Данный текст является ознакомительным фрагментом.