Двоично-троичный словарь

Бинарное дерево называется полностью сбалансированным, если оба его поддере­ва имеют примерно одинаковую высоту (или размер) и также являются сбалансиро­ванными. Высота сбалансированного дерева приблизительно равна legn, где п -• количество узлов в дереве.Время, необходимое для вычисления отношений in, add и delete на бинарных словарях, возрастает пропорционально высоте дерева. Поэтому все эти операции на сбалансированных словарях могут быть выполнены за время, пропорциональное log я. Логарифмическийрост затрат времени на проверку при­надлежности к множеству представляет собой значительное улучшение по сравнению со способом представления множеств в виде списков, при котором затраты времени растут пропорционально размерунабора данных. Но если дерево плохо сбалансиро­вано, эффективность доступа к словарю снижается. Б крайних случаях бинарный словарь вырождается в список, как показано на рис. 10.1. Форма словаря зависит от того, в какой последовательности в него вставлялись данные. В лучшем случае обес­печивается хорошая сбалансированность, при которой эффективность доступа про­порциональна log n, а в худшем случае эффективность доступа пропорциональна п. Анализ показывает, что в среднем, при условии, что любая последовательностьввода данных является равновероятной, эффективность выполнения отношений in, acid ж delete все равно остается пропорциональной log n. Поэтому, к счастью, эффектив­ность всреднем ближе к наилучшему, чем к наихудшему случаю. Но существуют и другие довольно простые схемы обеспечения хорошей сбалансированности дерева не­зависимо от последовательности данных. Такие схемы гарантируют эффективность

выполнения отношений in, add и delete, даже в худшем случае пропорциональную log n. Одной из них являются двоично-троичные (сокращенно 2-3) деревья, а дру­гой - AVL-деревья.

Двоично-троичное дерево определяется следующим образом. Оно является либо пустым, либо состоящим из единственного узла, либо представляет собой дерево, ко­торое соответствует следующим условиям.

• Каждый внутренний узел имеет два или три дочерних узла.

• Все листья находятся на одном и том же уровне.

Двоично-троичный словарь представляет собой двоично-троичное дерево, в кото­ром элементы данных хранятся в листьях, упорядоченных слева направо. (Пример такого дерева приведен на рис. 10.2.) Внутренние узлы содержат метки, которые обозначают минимальные элементы поддеревьев следующим образом.

• Если внутренний узел имеет два поддерева, то он содержит минимальный эле­мент второго поддерева.

• Если внутренний узел имеет три поддерева, то он содержит минимальные эле­менты второго и третьего поддеревьев.

Рис. 10.1. Полностью несбалансирован­ный бинарный словарь; эффективность доступа к нему снижается до уровня эффективности доступа к списку

Рис 10.2. Двоично-троичный словарь; указанный путь соответствует по­следовательности поиска элемента 10

216 Часть I.Язык Prolog

Для поиска элемента X в двоично-троичном словаре необходимо начинать с корня и переходить на нижний уровень, руководствуясь метками на внутренних узлах. Предположим, что корень содержит метки Ml и М2, В таком случае должны выпол­няться следующие действия:

• если X < Ml, то продолжать поиск в левом поддереве;

• иначе, если X < К2, то продолжать поиск в среднем поддереве;

• иначе продолжать поиск в правом поддереве.

Еще один вариант состоит в том, чтокорень содержит только одну метку, К. В таком случае, если X < М, то поиск должен продолжаться в левом поддереве, а иначе — в правом поддереве. Такие операции поиска продолжаются до тех пор, пока не будет достигнут уровень листьев, и в этот момент либо успешно обнаруживается элемент X, либо поиск завершается неудачей.

Поскольку все листья находятся на одном и том же уровне, двоично-троичное де­рево является идеально сбалансированным по отношению к значениям высоты своих поддеревьев. Все пути поиска от корня до любого листа имеют одинаковую длину, пропорциональную log л, где п — количество элементов, хранящихся в дереве.

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

Рис. 10.3. Вставка элементов е двоично-троичныйсловарь; береоо вначале растет в ширину, а затем — в высоту

Операцию вставки элементов в двоично-троичный словарь можно запрограммиро­вать как следующее отношение; add23( Tree, X, NewTree)

где NewTree — дерево, полученное в результате вставки элемента X в дерево Tree. Основная работа но вставке элементов будет передана двум вспомогательным отно­шениям, которые оба именуются как ins. Первое из них имеет следующие три па­раметра:

ins* Tree, X, NewTree)

где NewTree - результат вставки X в дерево Тгоо. Деревья Tree и NewTree имеют одинаковую высоту. Но, безусловно, не всегда возможно сохранить после вставки прежнюювысоту. Поэтому предусмотрено еще одно отношение ins с пятью парамет­рами, позволяющее учесть эту ситуацию, следующим образом:

ins ( Tree, X, NTa, Mb, HTb}

В данном случае после вставки элемента X в дерево Tree последнее разделяется на два дерева, NTa и NTb, имеющие такую же высоту, как и Tree. Здесь Mb является минимальным элементом дерева NTb. Пример ситуации, в которой дерево необходимо разбить на два, показан на рис. 10.4.

Глава 10. Усовершенствованные методы представления деревьев 217

NTa

Mb 6

NTb

Рис. 10.4. Пример, в котором объекты соответствуют отношению ins ( Tree, 6, NTa, Mb, NTb}

В разрабатываемой программе двоично-троичное дерево должно быть представле­но, в зависимости от его формы, следующим образом.

• nil представляет пустое дерево.

• 1 (X) представляет дерево с одним узлом — листом с элементом X.

• п2 (Т1, к, Т2) представляет дерево с двумя поддеревьями, Т1 ит2; М — ми­нимальный элемент Т2.

• пЗ(Т1, М2, 12, МЗ, ТЗ) представляет дерево с тремя поддеревьями, Tl, T2 и ТЗ; М2 - минимальный элемент Т2, а МЗ - минимальный элемент ТЗ.

Здесь Tl, T2 и ТЗ являются двоично-троичными деревьями.

Отношение между add23 и ins характеризуется тем, что если после вставки эле­мента дерево не растет вверх, то имеет место следующее правило:

add2 3( Tree, X, NewTree) :-ins ( Tree, X, NewTree).

Но если высота дерева после вставки увеличивается, то отношение ir-.s определяет два поддерева, 71 и 72, которые затем объединяются в более крупное дерево:

add23[ Tree, X, п2 ( Tl, М, 72) ) :-ins С Tree, X, Tl, И, Т2).

Отношение ins является более сложным, поскольку в нем должно учитываться много вариантов: вставка в пустое дерево, а дерево с одним узлом, в дерево типа :.2 или пЗ. Дополнительные промежуточные варианты возникают в результате вставки в первое, второе или третье поддерево. Соответственно, отношение ins определено как набор правил таким образом, что в каждом предложении, касающемся ins, рассмат­ривается один из вариантов. Некоторые из этих вариантов приведены на рис. 10.5. Варианты, показанные на данном рисунке, можно представить на языке Prolog сле­дующим образом.

Вариант А

ins( n2 I Т1, M, 12) X, п2( NT1,

gt( М, X), ins(Tl , X, NT1] .

М, Т2)) :-

% М Больше чем

X

Вариант Б

.ns( п2( Tl, К, Т2», X, лЗ( NTla, Mb, HTlb, К, Т2) } :-

gt{ и, :■::,

ins{ Ti, X, NTla, Mb, NTlb].

Вариант В

ins ( ri3 ( Tl, H2, T2, МЗ, T3], X, n2 ( NTla, Mb, NTlb), Ш gt£ M2, X) , ins( Tl, X, NTla, Mb, NTlb) .

n2 ( T2, МЗ, ТЗ))

218 Часть I. Язык Prolog

А)

Б)

м>х

ins{T1,X,NT1)

=>

м>х sfTI.X.NTIa.Mb.NTIb)

£к'

М2>Х

ins[T1,X, NTIa, Mb,NT1b)

Рис, 10.5. Некоторые варианты использования отношения ins: a) ins ( п2 <Т1, Я, Т2), X, г.2 (NT1, М, T2));6)ins( п2 {71, М, Т2) , X, пЗ (NTIa, Mb, STlb, N„ T2)l;

в) ins i пЗ (Tl,M2, Т2, Ю, ТЗ} , X, n.2 (NTIa,Mb, NTlbj,M2, п2 ( Т2, №. ТЗ)}

В листинге 10.1 приведена полная программа вставки в двоично-троичный сло­варь, а в листинге 10,2 приведена программа отображения двоично-троичных деревьев.

Листинг 10.1. Программа вставки в двоично-троичный словарь; в этой программе попытки вставки дублирующегося элемента завершаются неудачей

% Вставка в деоичко-тсоичный слозаоь

add23[ Tree, X, Treel) :-ins{ Tree, X_r Treel).

add23( Tree, X, n2{ Tl, MZ, T2}) ins( Tree, X_r Tl, M2, T2) ..

del23i Tree, X, Treel) :-add23( Treel, X, Tree).

4 Ввести X в дерево Tree, получив дерево Treel % Дерево растет в ширину

:- % Дерево растет в высоту Удалить X из дерева Tree, получив дерево Treel

ins( nil,х, ЦУ.) ) .

ins ( 1[А), X, 1(A), X, 1(Х)) :-gt ( X, А ) .

ins ( 1(A), X, 1(Х),А, 1(A)) :-gt( A, X) .

-

Т2} , х, п2 ( ЫТ1, И» Т2) )

ms( n2{ T1, gt( М, X) , ins( Tl, X, NTl).

Mb, NTlb, M, T2))

ins ! n2[ Tl, M, T2) , X, пЗ ( MTI gt; М, x) ,

ins ( Tl, X, NTla,Mb, NTlb) .

ins [ n2 ( Tl, M, T2 ) , X, n2 [ Tl, M, BT2] ) :-

gt{ x, M),

ins( T2, X, KT2). last n2 [ Tl, M_r T2) , S, n3 [ Tl, M, MT2a, Mb, NT2b) ) gt(X, M),

Глава 10. Усовершенствованные методы представления деревьев

ins I T2 , X, HT2a, Mb, NT2b) ,

ins ( n3 ( Tl, M2, T2, M3, ГЗ) , X, Г.ЗС NTl,M2, T2 , M3, T3}) :-gt ( И2, X) ,

ins [ Tl, x, NTl).

ins( n3( Tl, M2, T2, КЗ, T3), X, n2<ETla, Mb, NTlb), K2, nZ{ T2, M3, T3)l :-gt{ M2,x) , ins( Tl, X, HTla,Kb, NTlb).

ins( n3 ( Tl, M2, T2, КЗ, ТЗЬ X, n3 [ Tl, M2, NT2, МЗ, ТЗ) ) :-gt( x, M2), gt ( МЗ, х) , ins( T2, X, NT2).

insl пЗ ( Т1, М2, T2_r МЗ, ТЗ), X, п2 ( Т1, N2, ЫТ2а) , Mb, r\2 £ НТ2Ь, МЗ, ТЗ}):-gtl X, М2) , gt ( МЗ, X) , "inst T2, X, NT2a_f Mb, NT2b) .

ins[ n3( Tl, M2, T2, МЗ, ТЗ), X, п3 1 Т1, Н2, Т2, МЗ, NT3)) :-gt( X, МЗ), ins( тз, х, NT3).

ins[ пЗ ( Т1, М2, Т2, МЗ, ТЗ), X, п2( Т1, М2, Т2), МЗ, n2( NT3a, Mb, NT3b) > :-

gt ( ;•:, мз),

ins! ТЗ, X, НТЗа, Mb', NT3b) .

Листинг 10.2.Программа отображения двоично-троичного словаря (слева) и словарь, который приведен на рис. 10.2, отображенный с помощью этой программы (справа) ■ Отображение двоично-троичного словаря _____________________________________________________ show{Т} :-show[T, 0) ,

J

shOTa

nil,

show(1 (ft) ,H) :-

tab[H), write (ft), nl.

T-

show( n2[Tl,M,T2) , H) HI is H+b, show( T2, Hi), tab(H), write(--j, nl, tab[H), write(M), nl, tab[K) , write ( — ) , nl, shcw( Tl, Hi) .

show С n3{ Tl, M2, T2	КЗ
Hi is H+5,
show( T3, Hi)r
tab(H), write!-->,	nl,
tab(H), write(M3),	nl,
show( T2, Hi)r
tab{H) , write(M2) ,'	nl,
tab(H), write( —) ,	nl,
show( Tl, Hi).

T3) , H)

-

	--
		12 10	12 10
			1
		4 3	4 3 1

Часть I.Язык Prolog

В данной программе иногда происходит ненужный перебор с возвратами. Напри­мер, если выполнение отношения ins с гремя параметрами завершается неудачей, то вызывается отношение ins с пятью параметрами и при этом отменяется часть вы­полненной работы. Эту причину снижения эффективности можно легко устранить, например, переопределив отношение ins следующим образом: ins2; Tree, X, HewTrees)

где NewTrees - список, имеющий длину 1 или 3, который соответствует таким ус­ловиям: HewTrees = [ UewTree], если ins{ Tree, X, NewTree)

HewTrees = [ ЯТа, Mb, NTb], если ins ( Tree, X, ЫТа, Mb, NTb)

В связи с этим отношение add.23 должно быть переопределено таким образом:

add23C T, X, 11) :-ias2! Т, X, Trees), combine( Trees, TlJ.

Отношение combine должно формировать одно дерево, 71, из списка Trees.

Упражнения

10.1. Определите отношение
in! Item, Tree)

для поиска элемента Item в двоично-троичном словаре Tree.

10.2. Откорректируйте программу, приведенную в листинге 10.1, для предотвраще­
ния перебора с возвратами (определите отношения ins2 и combine).