Абсолютно готов к реализации ротации в дереве бинарного поиска C ++ - PullRequest
Новая
       12

Абсолютно готов к реализации ротации в дереве бинарного поиска C ++

0 голосов
/ 17 ноября 2018

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

contains () должно проверять, существует ли элемент где-то в дереве, и если этот элемент был найден search_threshold раз, поверните его на одну позицию выше в дереве.

Я какое-то время пробовал свое грязное решение, но оно работало не так, как нужно.На данный момент я просто снимал, чтобы получить действительно базовый пример работы ротации, когда перемещаемый узел не имеет дочерних элементов, но даже он, кажется, отбрасывает узлы.Любые советы, как вернуться на правильный путь? 

//BSTNode is a struct with
T element, 
BSTNode *left = NULL, 
BSTNode *right = NULL, 
BSTNode *parent = NULL, 
int search_count = 0

Сокращенный код следующим образом: 

template <typename T>
void BST< T >::rotateWithLeftChild(BSTNode *& k2)
{
    BSTNode *k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2 = k1;
}

template <typename T>
void BST< T >::rotateWithRightChild( BSTNode *& k2)
{
    BSTNode *k1 = k2->right;
    k2->right = k1->left;
    k1->left = k2;
    k2 = k1;
}

template <typename T>
void BST< T >::doubleWithRightChild( BSTNode *& k3 )
{
    rotateWithLeftChild( k3->right );
    rotateWithRightChild( k3 );
}

template <typename T>
void BST< T >::doubleWithLeftChild( BSTNode *& k3 )
{
    rotateWithRightChild( k3->left );
    rotateWithLeftChild( k3 );
}

template <typename T>
bool BST< T >::contains(const T& v, BSTNode *&t)
{
    // If the node doesn't exist, return false
    if (t == NULL)
        return false;
    // If the node exists, return true
    if (t->element == v)
    {
        // Increment search count
        t->search_count++;
        // If search count is above threshold,
        if (t->search_count >= threshold)
        {
            cout << "Search count above threshold" << endl;
            // Reset search count
            t->search_count = 0;

            if (t == root)
                return true;

            // Faaaaaairly confident that my bug is here
            if (t->left != NULL && t->right != NULL)
            {
                cout << "parent element: " << t->parent->element << endl;
                if (t == t->parent->left)
                    rotateWithLeftChild(t->parent);
            }
        }
        return true;
    }
    // Otherwise, return the OR of the children's contains()
    else
        return (contains(v, t->left) || contains(v,t->right));
}

1 Ответ

0 голосов
/ 17 ноября 2018

Начните с облегчения своей работы.

Влево и вправо должны быть уникальными ptrs. Родитель голый ptr.

Получить влево / вправо возвращает голый ptr. Снижение влево / вправо возвращает уникальный родительский элемент ptr, и null в уникальном дереве ptr'd.

Набор занимает уникальный ptr.

Поворот функций принимает уникальный ptr, а возвращает уникальный ptr.

Люди, которые вызывают функции поворота, должны отрываться от родителя, вращать это дерево, а затем возвращать его в родительский. 

BSTNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2 = k1;

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

Мы хотим перейти от: 

      a
  b      R
L  c

до: 

      b
  L      a
        c  R

Итак, в псевдокоде: 

up<Node> rot_left( up<Node> a ){
  auto b=a->snip_left();
  auto c=b->snip_right();
  a->set_left(std::move(c));
  b->set_right(std::move(a));
  return b;
}

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

Theae шаги могут быть выполнены без переписывания вашего кода для использования уникальных ptrs; достаточно иметь методы snip / set / get, которые поддерживают инварианты.

Из-за этого переписывания я подозреваю, что проблема в том, что ваш код поворота неправильно поддерживает родительские ptrs. Триада snip / set / get сделает это за вас, если вы будете использовать ее осторожно; уникальный ptr, но должен отличать операции владения (snip / set) от операций наблюдения (get).

...