Функция вставки для дерева AVL - PullRequest
Новая
       10

Функция вставки для дерева AVL

1 голос
/ 14 марта 2020

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

Это мой правый поворот: 

void RightRotate(NODE* Parent, NODE* N)
  {

    NODE* L = N->Left;
    NODE* A = L->Left;
    NODE* B = L->Right;
    NODE* C = N->Right;

      L->Right = N;
      N->Left = B;



      if(Parent == nullptr){
        Root = L;
      }
      else if (L->Key < Parent->Key){
        Parent->Left = L;
      }
      else{
        Parent->Right = L;
      }

      // 4. Update N's height:
      int HA , HB , HC;

      if(A == nullptr){
        HA = -1;
        }
      else{
          HA = A->Height;;
      }
      if(B == nullptr){
        HB = -1;
        }
      else{
          HB = B->Height;;
      }
      if(C == nullptr){
        HC = -1;
        }
      else{
          HC = C->Height;;
      }

      N->Height = 1 + max(HB , HC);



      L->Height = 1 + max(HA, N->Height);

  }// end of rightrotate(...)

Наряду с мой левый поворот: 

void LeftRotate(NODE* Parent, NODE* N)
{

    NODE* R = N->Right;
    NODE* A = N->Left;
    NODE* B = R->Left;
    NODE* C = R->Right;

    //2. Rotate:
    R->Left = N;
    N->Right = B;

    //3. Update Parent to the link:
    if(Parent == nullptr){
      Root = R;
      }
    else if(R->Key < Parent->Key){
      Parent->Left = R;
      }
    else{
      Parent->Right = R;
      }

    // Update N's height:
    int HA, HB, HC;

    if(A == nullptr){
        HA = -1;
        }
    else{
        HA = A->Height;
    }
    if(B == nullptr){
        HB = -1;
        }
    else{
        HB = B->Height;
    }
    if(C == nullptr){
        HC = -1;
        }
    else{
        HC = C->Height;
    }

    N->Height = 1 + max(HA , HB);



    R->Height = 1 + max(HC, N->Height);
}

Это вкладка, с которой я работаю, и мне нужна помощь, чтобы соединить все вместе со случаями вращений: 

  void insert(TKey key, TValue value)
  {
    NODE* prev = nullptr;
    NODE* cur = Root;

    stack<NODE*> nodes;

    //
    // 1. Search to see if tree already contains key:
    //
    while (cur != nullptr)
    {
      if (key == cur->Key)  // already in tree
        return;

      nodes.push(cur);  // stack so we can return later:

      if (key < cur->Key)  // search left:
      {
        prev = cur;
        cur = cur->Left;
      }
      else
      {
        prev = cur;
        cur = cur->Right;
      }
    }//while

    //
    // 2. if we get here, key is not in tree, so allocate
    // a new node to insert:
    // 
    NODE* newNode;
    newNode = new NODE();
    newNode->Key = key;
    newNode->Value = value;
    newNode->Height = 0;  // leaf node -> sub-tree of height 0:
    newNode->Left = nullptr;
    newNode->Right = nullptr;

    //
    // 3. link in the new node:

    if (prev == nullptr)
      Root = newNode;
    else if (key < prev->Key)
      prev->Left = newNode;
    else
      prev->Right = newNode;

    // 
    // 4. update size:
    //
    Size++;

    while( !nodes.empty() ){
       NODE* cur;
       cur = nodes.top();
       nodes.pop();
       int HL;
       int HR;
       if(cur->Left == nullptr){
          HL = -1;
          }
       else{
          HL = cur->Left->Height;
          }
       if(cur->Right == nullptr){
          HR = -1;
          }
       else{
           HR =  cur->Right->Height;
          }
      int newH = 1 + max(HL,HR);

      if(cur->Height == newH){
        break;
      }
      else if( (cur->Height) - (newH) == 1 || (cur->Height) - (newH) == -1 || (cur->Height) - (newH) == 0 ) {
        cur->Height = newH; // updates the new height.
        continue;
      }

      else{ // TODO Case conditions:

        if(cur->Left->Height > cur->Right->Height){ // case 1 and 2

        }
        else{ // case 3 and 4

        }

      }


    }// end while

  }

1 Ответ

0 голосов
/ 26 марта 2020
  1. Найдите несколько простых и простых примеров для случаев 1 - 4
  2. Кодируйте последовательность операций, запускающих каждый случай
  3. Нарисуйте или запишите, как каждый случай следует лечить.
  4. Реализация каждого случая

Для тестирования

Запуск тестовых случаев из точки 2 Реализация функции, которая проверяет ограничения AVL (разность высот и сортировка) Запуск большого количества случайных операций (вставка и удаление) для дерево при проверке ограничений для определения критических настроек
...