Дерево поиска

Двусвязный список

Каждый элемен

т двусвязного списка имеет два поля для указателей: один указательl содержит адрес предыдущего элемента списка, второй r содержит адрес следующего элемента списка. Двусвязный список можно просматривать как сначала, так и с конца

С любой стороны к нему можно добавлять элементы. Для этого списку ставят в соответствии два указателя: указатель на начало и указатель на конец списка.

Пример

//Описание типов и переменных_указателей

Type

Tbase = integer;

Tlink =^Trec;

Trec= Record

Inf: Tbase;

L, R: Tlink;

End;

Var

Start, Kon: Tlink;

// Основные операции для двусвязного списка

1 Создание пустого списка

Start: = nil; kon: = nil;

2 Добавление элемента в начало списка

Procedure In_Dspisok (el_list: tbase);

Var P: tlink;

Begin

New(p);

p^.inf: =El_list;

If (start = nil) and (kon = nil) then

Begin

p^.l: = nil;

p^.r: = nil;

Start: =p;

Kon: =p;

End

Else

Begin

p^.r: =start;

Start^.l: = p;

p^.l: = nil;

Start: =p;

End; // if

End; // In_Dspisok

//=========

Двусвязный список можно представить в вид кольцевого(циклического) списка с указателем на начало списка.

Пример. Подсчитать количество звеньев в кольцевом списке.

Алгоритм

Количество=0;

Если < список не пуст> то

{ Текущему указателю присвоить значение указателя начала списка;

Повторить

{ Количество увеличить на 1;

< текущий указатель>: = < значение указателя предыдущего элемента> }

До < значение текущего указателя равно значению указателя начала списка> }

Реализация

K: = 0;

If start < > nil then // < список не пуст

Begin

P: = start; // Текущему указателю присвоить значение указателя начала списка

Repeat

Inc(k); // Количество увеличить на 1;

P: =P^.l; // текущему указателю присвоить значение указателя предыдущего элемента

Untl p=start// значение текущего указателя равно значению указателя начала списка

End;

Write(k);

Деревья

Частным случаем многосвязного списка является дерево. Дерево – это непустое конечное множество элементов, один из которых называется корнем, а остальные делятся на несколько непересекающихся подмножеств, каждое из которых является деревом. Каждый элемент дерева называется узлом дерева. Линия связывающая пару узлов дерева, называется ветвью. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются листьям и. Узлы, на которые ссылается некоторый узел дерева, называются его потомками. Деревья, у которых узлы могут иметь не более двух потомков, называются бинарными.

Дерево поиска

Если двоичное дерево организовано таким образом, что для каждого узла P все значения (ключи) в левом поддереве меньше значения в узле P, а все значения а правом поддереве не меньше значения в P, то такое дерево называется деревом поиска.

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

двигаясь, начиная от корня, и переходя на левое или правое поддерево каждого узла в зависимости от значения этого элемента.