Программирование на языке Пролог для искусственного интеллекта



         

Двоично - троичные справочники - часть 2


  • каждая внутренняя вершина имеет две или три дочерних вершины, и
  • все листья дерева находятся на одном и том же уровне.
  • Двоично-троичным (2-3) справочником называется 2-3 дерево, все элементы данных которого хранятся в листьях и упорядочены слева направо. На рис. 10.2 показан пример. Внутренние вершины содержат метки, равные минимальным элементам тех или иных своих поддеревьев, в соответствии со следующими правилами:

  • если внутренняя вершина имеет два поддерева, то она содержит минимальный элемент второго из них;
  • если внутренняя вершина имеет три поддерева, то она содержит минимальные элементы второго и третьего поддеревьев.
  • fig10_2.gif (3052 bytes)

    Рис. 10. 2.  2-3 справочник. Отмеченный путь показывает процесс поиска элемента 10.

    При поиске элемента Х в 2-3 справочнике мы начинаем с корня и двигаемся в направлении самого нижнего уровня, руководствуясь при этом метками внутренних вершин дерева. Пусть корень содержит метки Ml и М2, тогда

  • если Х < M1, то поиск продолжается в левом поддереве, иначе
  • если Х < М2, то поиск продолжается в среднем поддереве, иначе -
  • в правом поддереве.
  • Если в корне находится только одна метка М, то переходим к левому поддереву при Х < М и к правому поддереву - в противоположном случае. Продолжаем применять сформулированные выше правила, пока не окажемся на самом нижнем уровне дерева, где и выяснится, найден ли элемент X, или же поиск потерпел неудачу.

    Так как все листья 2-3 дерева находятся на одном и том же уровне, 2-3 дерево идеально сбалансировано с точки зрения глубины составляющих его поддеревьев. Все пути от корня до листа, которые мы проходим при поиске, имеют одну и ту же длину порядка log n, где n - число элементов, хранящихся в дереве.

    При добавлении нового элемента данных 2-3 дерево может расти не только в глубину, но и в ширину. Каждая внутренняя вершина, имеющая два поддерева, может приобрести новое поддерево, что приводит к росту вширь. Если же, с другой стороны, у вершины уже есть три поддерева, и она должна принять еще одно, то она расщепляется на две вершины, каждая из которых берет на себя по два из имеющихся четырех поддеревьев.


    Содержание  Назад  Вперед