Список реализован с использованием двоичного дерева по порядку - PullRequest
Новая
       12

Список реализован с использованием двоичного дерева по порядку

2 голосов
/ 31 октября 2009

Для нового задания по информатике мы должны реализовать список / массив с использованием двоичного дерева по порядку. Я просто хотел бы предложение, а не решение.

Идея состоит в том, чтобы иметь двоичное дерево, узлы которого доступны через индексы, например 

t = ListTree()
t.insert(2,0) # 1st argument is the value, 2nd the index to insert at
t.get(0) # returns 2

Класс Node, в котором хранятся значения, не подлежит изменению, но имеет свойство size, которое содержит общее количество нижестоящих дочерних элементов, а также left, right и value, которые указывают на дочерние элементы и хранилище. значение соответственно.

Моя главная проблема в настоящее время - отслеживание индекса - поскольку нам не разрешено хранить индекс узла в самом узле, я должен полагаться на его обход. Поскольку при обходе я всегда начинаю с левого узла, я еще не придумал, как рекурсивно выяснить, по какому индексу мы сейчас находимся.

Любые предложения приветствуются.

Спасибо!

Ответы [ 5 ]

1 голос
/ 31 октября 2009

Я не думаю, что вы хотите хранить индекс, а просто размер каждого поддерева. Например, если вы хотите найти 10-й элемент в списке, а левые и правые подчиненные имеют по 7 элементов в каждом, вы должны знать, что корень - это элемент из восьми (так как он двоичный по порядку) и первый элемент из правого поддерева 9-го. вооружившись этим знанием, вы вернетесь в нужное поддерево, ища 2-й элемент.

НТН

1 голос
/ 31 октября 2009

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

0 голосов
/ 19 ноября 2009

Очень простое решение - выполнить GetFirst (), чтобы получить первый узел дерева (это просто поиск самого левого узла дерева). Если ваш индекс N равен 0, верните первый узел. В противном случае вызовите GetNodeNext () N раз, чтобы получить соответствующий узел. Это не очень эффективно, так как доступ к узлу по индексу занимает O (N Lg N) времени. 

Node *Tree::GetFirstNode()
{
    Node *pN,*child;
    pN=GetRootNode();
    while(NOTNIL(child=GetNodeLeft(pN)))
    {
        pN=child;
    }
    return(pN);
}


Node *Tree::GetNodeNext(Node *pNode)
{
    Node *temp;

    temp=GetNodeRight(pNode);
    if(NOTNIL(temp))
    {
        pNode=temp;
        temp=GetNodeLeft(pNode);
        while(NOTNIL(temp))
        {
            pNode=temp;
            temp=GetNodeLeft(pNode);
        }
        return(pNode);
    }
    else
    {
        temp=GetNodeParent(pNode);
        while( (NOTNIL(temp)) && (GetNodeRight(temp)==pNode) )
        {
            pNode=temp;
            temp=GetNodeParent(pNode);
        }
        return(temp);
    }
}
0 голосов
/ 31 октября 2009

Должно ли дерево быть сбалансированным? Должен ли алгоритм быть эффективным?

Если нет, то самое простое - создать дерево, в котором все левые дочерние элементы равны нулю, т. Е. Дерево, переходящее в связанный список.

Чтобы вставить, рекурсивно посмотрите, перейдите к нужному потомку, а затем обновите размер узла на обратном пути. Нечто подобное (псевдокод) 

function insert(node, value, index, depth)
    if depth < index
        create the rightchild if necessary
        insert( rightchild, value, index, depth + 1)
    if depth == size
        node.value = value
    node.size = rightchild.size + 1

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

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

Например, пустой список имеет один узел, без дочерних элементов со значением null и размером 0.

Скажем, вы хотите вставить «привет» в индекс 1034. Затем вы хотите получить дерево, корень которого имеет двух дочерних элементов, с размерами 1024 и 10. У левого дочернего элемента нет реальных дочерних элементов, но у правого узла есть правый дочерний элемент собственного размера 2. (подразумевается левый размер 8). Этот узел, в свою очередь, имеет одного правого дочернего элемента размера 0 со значением «привет». (Этот список имеет индекс на основе 1, но индекс на основе 0 аналогичен.)

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

0 голосов
/ 31 октября 2009

Ну, у узла в двоичном дереве не может быть значения и индекса. Они могут иметь несколько фрагментов данных, но дерево может быть связано / построено только на одном.

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

...