Динамические структуры данных. Деревья, их применение
Дерево - множество, состоящее из элемента, называемого корнем, и конечного (возможно пустого) множества деревьев, называемых поддеревьями данного дерева. Дерево, так же как и список, реализуется прежде всего на динамических структурах, т.е. узел дерева содержит два поля-ссылки – на левое и правое поддерево для двоичного дерева и на брата и старшего сына для дерева общего вида. Дерево либо пусто, либо состоит из узла, содержащего указатели на пересекающиеся деревья, называемые поддеревьями
ЗАПИСИ, содержащие данные и указатели, является вершинами
Вершина, на которую не содержится указателя ни в одной другой вершине, считается корнем
Вершина В, на которую имеется указатель в вершине А, называется непосредственным потомком вершины А, при этом вершина А называется непосредственным предком(отцом) вершины В. Вершин, являющиеся непосредственными потомками одной и той же вершины, называются братьями, вершину, не имеющую потомков, называют терминальной или листом. Нетерминальные вершины называются так же внутренними. Уровень вершины(длинна пути к вершине) считается число ребер, которое нужно пройти, что бы попасть в нее из коня уровень корня равен 0
Дерево называют упорядоченным, если для дерева важен порядок ребер, исходящих из вершины. Если же принимается во внимание лишь ориентация вершин, то дерево ориентированное. Например, если два дерева упорядочены, то они являются различными. Если же они ориентированы, то они считаются одинаковыми.
Упорядоченное множество, состоящее из n деревьев (n>=0) называется лесом.
Дерево, в котором вершин имеют не более двух потомком, называется двоичным (бинарным) деревом. Бинарное дерево называется упорядоченным, если для каждого его узла, имеющего поддеревья, корень больше левого поддерева и меньше правого Двоичное дерево имеет два поддерева –левое(первое) и правое(второе).
Дерево, каждая вершина которого имеет не более трёх потомков, называется тернарным, не более четырех – тетрарным. Дерево, у которого число потомков для каждой вершины не может превышать число n, называет n-арным.
Любой лес n-арных деревьев можно представать в виде двоичного дерева. При этом в каждой вершине указатель на левое поддерево ссылается на первого непосредственного потомка, а указатель на правое – на первого младшего брата, если это обычная вершина, и на корень следующего дерева леса, если это корень.
Дерево считается сбалансированным, если для каждой его вершины число число вершин в ее левых и правых поддеревьях отличается не больше чем на 1.
Наиболее часто используемым является двоичное дерево. Рассмотрим алгоритм обхода двоичного дерева по всем вершинам. Пусть например в каждой вершине дерева, кроме указателей на поддеревья, хранятся символы.
К основным действиям над деревьями:
-вставка элеента в дерево
-обход дерева
-удаление элемента из дерева
type
tree_ptr=^tree; //tree_ptr тип данных адресса области памяти, в которй хранится значение типа tree
tree=
record описываем запись типа три
c: char;
left, right: tree_ptr;
end;
Данное дерево организовано таким образом, что для каждого узла все ключи (значения узлов) его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева больше. Такой способ построения дерева называется деревом поиска или двоичным упорядоченным деревом.
С помощью дерева поиска можно организовать эффективный способ поиска, который значительно эффективнее поиска по списку.
Поиск в упорядоченном дереве выполняется по следующему рекурсивному алгоритму:
· Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева:
· если ключи совпадают, поиск завершен;
· - если ключ в корне больше искомого, выполнить поиск в левом поддереве;
· - если ключ в корне меньше искомого, выполнить поиск в правом поддереве.
- Если дерево пусто, то искомый элемент не найден.
Function find(root:tree; key:integer; var p, paent: tree):Boolean;
begin
p:=root;
while p<>nil do begin
if key=p^.inf then begin (узел с таким ключем есть)
Find =true
exit;
end;
Parent:=p (запомнить указатель на предка)
If key<p.inf then
P:=p^.left (спуститься влево)
Else p:=p^.right;
End;
find:=false;
end;
nill пустота
p^.inf узел , вершина
p указатель на предка
Для того чтобы вставить узел, необходимо найти его место. Для этого мы сравниваем вставляемый ключ с корнем, если ключ больше, чем ключ корня, уходим в правое поддерево, а иначе – в левое. Тем же образом продвигаемся дальше, пока не дойдем до конечного узла (листа). Сравниваем вставляемый ключ с ключом листа. Если ключ меньше ключа листа, то добавляем листу левого сына, а иначе – правого сына. Например, необходимо вставить в дерево, изображенное на рисунке, узел с ключом 5.
Сравниваем 5 с ключом корня; 5<10, следовательно, уходим в левое поддерево. Сравниваем 5 и 6; 5<6, спускаемся влево. Следующий узел является конечным (листом). Сравниваем 5 и 1; 5>1, следовательно, вставляем правого сына. Получим дерево с новым узлом, которое сохранило все свойства дерева поиска.
Если узел является конечным (то есть не имеет потомков), то его удаление не вызывает трудностей, достаточно обнулить соответствующий указатель узла-родителя. Сложнее всего случай, когда у удаляемого узла есть оба потомка.
Есть простой особый случай: если у правого потомка удаляемого узла нет левого потомка, удаляемый узел заменяется на своего правого потомка, а его левый потомок подключается вместо отсутствующего левого потомка к замещающему узлу. Рассмотрите этот случай на рисунке, должно стать понятней.
procedure del ( var root : tree ; key : integer );
var
p : tree ; {удаляемый узел}
parent : tree ; {предок удаляемого узла}
y : tree ; {узел, заменяющий удаляемый}
function spusk(p:tree):tree;
var
y : tree ; {узел, заменяющий удаляемый}
pred:tree; { предок узла “y”}
begin
y:=p^.right;
if y^.left=nil then y^.left:=p^.left {1}
else {2}
begin
repeat
pred:=y; y:=y^.left;
until y^.left=nil;
y^.left:=p^.left; {3}
pred^.left:=y^.right; {4}
y^.right:=p^.right; {5}
end;
spusk:=y;
end;
begin
if not find(root, key, p, parent) then {6}
begin writeln(‘ такого элемента нет ’); exit; end;
if p^.left=nil then y:=p^.right {7}
else
if p^.right=nil then y:=p^.left {8}
else y:=spusk(p); {9}
if p=root then root:=y {10}
else {11}
if key<parent^.inf then
parent^.left:=y
else parent^.right:=y;
dispose(p); {12}
end.
В функцию del передаются указатель root на корень дерева и ключ key удаляемого элемента. С помощью функции find определяются указатели на удаляемый элемент p и его предка parent . Если искомого элемента в дереве нет, то выдается сообщение ( {6}) .
В операторах {7}-{9} определяется указатель на узел y , который должен заменить удаляемый. Если у узла p нет левого поддерева, на его место будет поставлена вершина (возможно пустая) его правого поддерева ({7}).
Иначе, если у узла p нет правого поддерева, на его место будет поставлена вершина его левого поддерева ({8}).
В противном случае, когда оба поддерева существуют, для определения замещающего узла вызывается функция spusk , выполняющая спуск по дереву ({9}).
В этой функции первым делом проверяется особый случай, описанный выше ({1}). Если же этот случай (отсутствие левого потомка у правого потомка удаляемого узла) не выполняется, организуется цикл ({2}), на каждой итерации которого указатель на текущий элемент запоминается в переменной pred , а указатель y смещается вниз и влево до того момента, пока не станет ссылаться на узел, не имеющий левого потомка (он-то нам и нужен).
В операторе {3} к этой пустующей ссылке присоединяется левое поддерево удаляемого узла. Перед тем как присоединять к этому узлу правое поддерево удаляемого узла ({5}), требуется «пристроить» его собственное правое поддерево. Мы присоединяем его к левому поддереву предка узла y , заменяющего удаляемый ({4}), поскольку этот узел перейдет на новое место.
Функция spusk возвращает указатель на узел, заменяющий удаляемый. Если мы удаляем корень дерева, надо обновить указатель на корень ({10}), иначе – присоединить этот указатель к соответствующему поддереву предка удаляемого узла ({11}).
После того как узел удален из дерева, освобождается занимаемая им память ({12}).
Двоичное деревво можнно обойти тремя пособоми
1 прямой оюход(сверху вниз):
· Попасть в корень
· Обойти левое поддерево
· -обойти правое поддерево
2 обратный обход (снизу вверх)
· Обойти левое поддерево
· Попасть в корень
· Обойти правое поддерево
3 концевой обход( слева направо)
· Обойти левое поддерево
· Обойти правое поддерево
· Попасть в корень
Procedure pass_dir ( t:tree_ptr); //процедура прямого обхода дерева
Паметр t типа tree_ptr –указатель на корень дерева или поддерева, обход которого производится
Begin
if t<>nill then
begin
write(t^.c);
pass_dir(t^.left);
pass_dir(t^.right);
end;
end.
Procedure pass_back ( t:tree_ptr); //процедура обратного обхода дерева
Паметр t типа tree_ptr –указатель на корень дерева или поддерева, обход которого производится
Begin
if t<>nill then
begin
pass_back(t^.left);
write(t^.c);
pass_back(t^.right);
end;
end.
Procedure pass_end ( t:tree_ptr); //процедура концевого обхода дерева
Паметр t типа tree_ptr –указатель на корень дерева или поддерева, обход которого производится
Begin
if t<>nill then
begin
pass_end(t^.left);
pass_end(t^.right);
write(t^.c);
end;
end.
Тип данных указатель.
Указатель - это ячейка памяти, хранящая адрес. В PascalABC.NET указатели делятся на типизированные (содержат адрес ячейки памяти данного типа) и бестиповые (содержат адрес оперативной памяти, не связанный с данными какого-либо определенного типа).
Тип указателя на тип T имеет форму ^T, например:
type pinteger = ^integer;
var p: ^record r,i: real end;
Бестиповой указатель описывается с помощью слова pointer.
Для доступа к ячейке памяти, адрес которой хранит типизированный указатель, используется операция разыменования ^:
var
i: integer;
pi: ^integer;
...
pi := @i; // указателю присвоили адрес переменной i
pi^ := 5; // переменной i присвоили 5
Операция разыменования не может быть применена к бестиповому указателю.
Типизированный указатель может быть неявно преобразован к бестиповому:
var
p: pointer;
pr: ^real;
...
p := pr;
Обратное преобразование также может быть выполнено неявно:
pr := p;
pr^ := 3.14;
Указатели можно сравнивать на равенство (=) и неравенство (<>). Для того чтобы отметить тот факт, что указатель никуда не указывает, используется стандартная константа nil (нулевой указатель) : p :=nil.
Внимание! Ввиду особенностей платформы .NET тип T типизированного указателя не должен быть ссылочным или содержать ссылочные типы на каком-то уровне (например, запрещены указатели на записи, у которых одно из полей имеет ссылочный тип). Причина такого ограничения проста: указатели реализуются неуправляемым кодом, который не управляется сборщиком мусора. Если в памяти, на которую указывает указатель, содержатся ссылки на управляемые переменные, то они становятся недействительными после очередной сборки мусора. Исключение составляют динамические массивы и строки, обрабатываемые особым образом. То есть, можно делать указатели на записи, содержащие в качестве полей строки и динамические массивы.