Теория и реализация языков программирования



         

Таблицы на деревьях


Рассмотрим еще один способ организации таблиц символов с использованием двоичных деревьев.

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

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

\prec
, то есть некоторое транзитивное, антисимметричное и антирефлексивное отношение. Таким образом, для произвольной пары идентификаторов id1 и id2 либо
id_1 \prec id_2
, либо
id_2 \prec id_1
, либо id1 совпадает с id2.


Рис. 7.5. 

Каждой вершине двоичного дерева, представляющего таблицу символов, сопоставим идентификатор. При этом, если вершина (которой сопоставлен id) имеет левого потомка (которому сопоставлен idL), то

id_L \prec id
; если имеет правого потомка (idR), то
id \prec id_R
. Элемент таблицы изображен на рис. 7.5.

Поиск в такой таблице может быть описан следующей функцией:

struct TreeElement * SearchTree(String Id, struct TreeElement * TP) {int comp; if (TP==NULL) return NULL; comp=IdComp(Id,TP->IdentP); if (comp<0) return(SearchTree(Id,TP->Left)); if (comp>0) return(SearchTree(Id,TP->Right)); return TP; }

где структура для для элемента дерева имеет вид

struct TreeElement {String IdentP; struct TreeElement * Left, * Right; };

Занесение в таблицу осуществляется функцией

struct TreeElement * InsertTree(String Id, struct TreeElement * TP) {int comp=IdComp(Id,TP->IdentP); if (comp<0) return(Fill(Id,TP->Left, &(TP->Left))); if (comp>0) return(Fill(Id,TP->Right, &(TP->Right))); return(TP); }

struct TreeElement * Fill(String Id, struct TreeElement * P, struct TreeElement ** FP) { if (P==NULL) {P=alloc(sizeof(struct TreeElement)); P->IdentP=Include(Id); P->Left=NULL; P->Right=NULL; *FP=P; return(P); } else return(InsertTree(Id,P)); }




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