Как рассчитать размер поддерева в куче бинарного дерева? - PullRequest
Новая
       23

Как рассчитать размер поддерева в куче бинарного дерева?

0 голосов
/ 28 апреля 2019

Я реализую структуру данных кучи. ADT кучи - это полное двоичное дерево, но при реализации кода куча хранится в массиве (поэтому она имеет итератор произвольного доступа). Я пытаюсь реализовать функцию, которая задает индекс для корня поддерева, он может вычислить размер этого поддерева (указан размер всего дерева).

Ниже я включил версию функции, которую написал для выполнения этой задачи. Я написал рекурсивную функцию, которая либо рекурсивно вычисляет размер поддерева, добавляя размер левого поддерева и правого поддерева плюс единицу, либо, если это лист, возвращает 1. Хотя это выполнит мою задачу, я думаю, что это приведет к O (n) временной сложности, поскольку для расчета размера поддерева ему необходимо посетить каждый индекс. 

typedef unsigned int uint;

template <typename T>
/**
 * @brief sizeOfHeapSubtree - Calculate the size of a subtree of heap from the
 *  root index
 * @param size - the total size of the heap array
 * @param root - the index of the root of the heap subtree
 * @return the size of the heap subtree starting from the root index
 */
uint sizeOfHeapSubtree(T a[], uint size, uint root){
    if(isLeaf(a, size, root)){
        //Base case: if the root index of the subtree is a leaf, size is 1
        return 1;
    } else {
        //Recursive case: if the root index of the subtree is NOT a leaf, 
        //                size is leaf subtree's size + right subtree's size
        uint leftSubtreeSize;
        uint rightSubtreeSize;

        uint left = leftChildIndex(a, size, root);
        leftSubtreeSize = sizeOfHeapSubtree(a, size, left);

        uint right = rightChildIndex(a, size, root);
        if(right < size)
            rightSubtreeSize = sizeOfHeapSubtree(a, size, right);
        else
            rightSubtreeSize = 0;

        return leftSubtreeSize + rightSubtreeSize + 1;
    }
}

Учитывая тот факт, что куча хранится в массиве, а размер всего дерева известен, я думаю, что я могу рассчитать размер поддерева, начиная с индекса с помощью математического вычисления или некоторых других методов, которые этого не делают. требуют пересечения массива.

У кого-нибудь есть идеи?

...