Нахождение последнего элемента двоичной "кучи"

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

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

Для двоичной "кучи", сохраненной в древовидной структуре, эта информация не так очевидна, но потому что это - полное двоичное дерево, она может быть вычислена. Например, в полном двоичном дереве с 4 элементами, точка вставки всегда будет правильным ребенком покинутого ребенка корневого узла. Узел для использования для удаления всегда будет покинутым ребенком покинутого ребенка корневого узла. И для любого данного произвольного древовидного размера, дерево будет всегда иметь определенную форму с четко определенной вставкой и точками удаления. Поскольку дерево является "полным двоичным деревом" с определенной структурой для любого данного размера, очень возможно вычислить местоположение вставки/удаления в O (1) время. Однако выгода - то, что, даже когда Вы знаете, где это структурно, Вы понятия не имеете, где узел будет в памяти. Так, необходимо пересечь дерево для получения до данного узла, который является O (зарегистрируйте n), процесс, делающий всех, вставляет, и удаления минимум O (зарегистрируйте n), повреждая обычно желаемый O (1) поведение. Любой поиск ("в глубину", или некоторый другой) будет, по крайней мере, O (зарегистрируйте n), также из-за пересекающейся отмеченной проблемы и обычно O (n) из-за случайной природы полуотсортированной "кучи".

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

реализация, которую, кажется, мне является самым легким понять с низкой памятью и дополнительным кодированием наверху, должна просто использовать нормальную простую структуру двоичного дерева (использующий pRoot и Узел, определенный как [данные, родитель, pLeftChild, pRightChild]) и добавлять два дополнительных указателя (pInsert и pLastNode). pInsert и pLastNode будут и обновлены во время вставки и подпрограмм удаления для держания их в курсе, когда данные в структуре изменятся. Эта реализация дает O (1) доступ и к точке вставки и к последнему узлу структуры и должна позволить сохранение полного O (1) поведение и во вставке и удалениях. Стоимость реализации является двумя дополнительными указателями и некоторым незначительным дополнительным кодом в подпрограммах вставки/удаления (иначе, минимальный).

РЕДАКТИРОВАНИЕ : добавленный псевдокод для O (1) вставляет ()

, Вот псевдо код для подпрограммы вставки, которая является O (1) в среднем:

define Node = [T data, *pParent, *pLeft, *pRight]

void insert(T data)
{
    do_insertion( data );   // do insertion, update count of data items in tree

    # assume: pInsert points node location of the tree that where insertion just took place
    #   (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process)

    int N = this->CountOfDataItems + 1;     # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion

    p = new Node( <null>, null, null, null);        // new empty node for the next insertion

    # update pInsert (three cases to handle)
    if ( int(log2(N)) == log2(N) )
        {# #1 - N is an exact power of two
        # O(log2(N))
        # tree is currently a full complete binary tree ("perfect")
        # ... must start a new lower level
        # traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion
        pInsert = pRoot;
        while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; }    # log2(N) iterations
        p->pParent = pInsert;
        pInsert->pLeft = p;
        }
    else if ( isEven(N) )
        {# #2 - N is even (and NOT a power of 2)
        # O(1)
        p->pParent = pInsert->pParent;
        pInsert->pParent->pRight = p;
        }
    else 
        {# #3 - N is odd
        # O(1)
        p->pParent = pInsert->pParent->pParent->pRight;
        pInsert->pParent->pParent->pRight->pLeft = p;
        }
    pInsert = p;

    // update pLastNode
    // ... [similar process]
}

Так, вставьте (T), O (1) в среднем: точно O (1) во всех случаях кроме тех случаев, когда дерево должно быть увеличено одним уровнем, когда это - O (регистрируют N), который происходит каждый журнал N вставки (принимающий удаления). Добавление другого указателя (pLeftmostLeaf) могло сделать, вставляют () O (1) для всех случаев, и избегает возможного патологического случая переменной вставки & удаление в полном полном двоичном дереве. (Добавляющий pLeftmost оставлен как осуществление [это довольно легко].)

Как насчет того, чтобы работать поиск в глубину , посещая покинутого ребенка перед правильным ребенком, определить высоту дерева. После этого первый лист, с которым Вы встречаетесь с более короткой глубиной или родителем с пропавшим ребенком, указал бы, куда необходимо поместить новый узел перед "пузырением".

подход поиска в глубину (DFS) выше не предполагает знание общего количества узлов в дереве. Если эта информация доступна, то мы можем "увеличить масштаб" быстро к желаемому месту путем использования свойств полные двоичные деревья :

Позволяют N быть общим количеством узлов в дереве, и H быть высотой дерева.

Некоторые значения ( N, H) (1,0), (2,1), (3,1), (4,2)..., (7,2), (8, 3). Общая формула, связывающая эти два, , H = перекрывает [log2 ( N+1)] - 1. Теперь, учитывая только [1 121] N, мы хотим пересечь от корня до положения для нового узла в наименьшем количестве количества шагов, т.е. без любого "отслеживания в обратном порядке". Мы сначала вычисляем общее количество узлов M в идеальное двоичное дерево из высоты , H = перекрывает [log2 ( N+1)] - 1, который является M = 2^ ( H+1) - 1.

0 0 0 0 0 X 0 0 <--- represents the last level in our tree, X marks the spot!
          ^
L L L L R R R R <--- at level 0, proceed to the R child
L L R R L L R R <--- at level 1, proceed to the L child
L R L R L R L R <--- at level 2, proceed to the R child 
          ^                      (which is the position of the new node)
          this column tells us
          if we should proceed to the L or R child at each level