Принципы размещения бинарного дерева в памяти ЭВМ

1. БД располагается в динамической памяти. Каждая вершина БД представляет собой СД типа «запись», содержащую информационную часть и адреса сыновей. Память под вершину БД выделяется по мере надобности при построении БД и освобождается при исключении вершины. Адрес корня дерева находится в специальной ячейке динамической памяти, адрес которой хранится в статической памяти. БД (см. рис.21)может быть представлено в памяти так, как показано на рис.22.

2. Для хранения вершин БД используется СД типа «массив». Массив может располагаться в статической или динамической памяти. Элементы массива представляют собой СД типа «запись», содержащую информационную часть и адреса сыновей вершины БД. Индекс элемента массива, содержащего корень дерева, находится в специальной ячейке динамической памяти, адрес которой хранится в статической памяти. Элементы массива, не являющиеся вершинами БД, объединяются в список свободных элементов (ССЭ), на первый элемент которого указывает правый сын первого элемента массива. При включении элемента в БД берется первый элемент ССЭ, а исключаемый элемент заносится в начало ССЭ. БД (рис.21) может быть представлено в памяти так, как показано на рис.23. При таком способе в одном массиве может быть размещено несколько БД.

3. Для хранения вершин БД используется СД типа «массив». Массив может располагаться в статической или динамической памяти. Элементы массива представляют собой СД типа «запись», содержащую информационную часть вершны БД и признак использования элемента массива — 1 — если элемент содержит вершину БД, 0 — если элемент свободен. Корнем дерева является элемент массива с индексом 1, индекс левого сына вычисляется по формуле i*2, где i — индекс отца, а правый сын располагается в следующем (i*2 + 1) элементе массива. БД (см. рис.21) может быть представлено в памяти так, как показано на рис.24.

Статическая адрес ячейки, содержащей