Как работает сортировка вставки для массива BST? - PullRequest
Новая
       4

Как работает сортировка вставки для массива BST?

1 голос
/ 18 ноября 2009

Я пытался сделать это рекурсивно .. Родительское целое число varaible будет похоже на i, в соответствии с формулой, 2*i +1 для leftChild и 2*i +2 для права. 

void BST::insert(const data &aData)
{
    if ( items[Parent].empty ) 
    {
        items[Parent].theData = aData;
        items[Parent].empty = false;
    }
    else if ( aData < items[Parent].theData )
    {
        Parent = 2 * Parent + 1;
        if ( Parent >= maxSize ) this->reallocate();
        this->insert(aData);
    }
    else
    {
        Parent = (2 * rightChild++)+ 2;
        if ( Parent >= maxSize ) this->reallocate();
        this->insert(aData);
    }
}

Отлично работает при вставке элементов, которые меньше оригинального родителя ... Но когда я нахожу что-то большее, все облажается: x 

void BST::reallocate()
{
    item *new_array = new item[maxSize*2];

    for ( int array_index = 0; array_index < maxSize; array_index++ ) 
    {
        if ( ! items[array_index].empty )
        {
            new_array[array_index].theData = items[array_index].theData;
        }
    }
    maxSize *= 2;
    delete [] items;

    items = NULL;
    items = new_array;
}

Вот мой ctor, так что никто больше не смущается, чем я: 

BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0),
leftChild(0), rightChild(0)
{
    items->empty = true;
    maxSize = capacity;
}
private:
    int size;  // size of the ever growing/expanding tree :)
    int Parent;
    int maxSize;    
    int leftChild;
    int rightChild;
    struct item
    {
        bool empty;
        data theData;
    };
    item *items;    // The tree array

Функция вставки, представленная выше, на самом деле лучшая, которую я могу получить .. 

                                 R
                                / \
                               /   \
                              /     \
                             L       X
                            / \     / \
                           J   V   K   T   <--The only out of place node.
                          / \   \
                         / NULL  \
                        G        /
                                P

При вставке: R, L, J, G, X, K, V, P, T в таком порядке

1 Ответ

1 голос
/ 24 ноября 2009

Я подозреваю, что ваша проблема в этой строке: 

    Parent = (2 * rightChild++)+ 2;

Почему вы используете rightChild вместо (2 * Parent) + 2?

Чтобы прояснить ситуацию, вы можете захотеть добавить несколько простых встроенных функций в ваш класс для вычисления индексов левого / правого потомка и родителя с учетом индекса: 

inline int getLeftChildIndex(int nodeNdx) { return (nodeNdx * 2) + 1; }
inline int getRightChildIndex(int nodeNdx) { ... }
inline int getParentIndex(int nodeNdx) { ... }

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

...