Реализация дерева AVL с использованием списка

Question

Так что я осуществил бинарное дерево поиска с использованием параметризованных списка т.е.

List<Node> tree = new List<>(); 

Дерево прекрасно работает. Сам узел ничего не знает о своем родителе или детях. Это связано с тем, что я вычисляю местоположения на основе индекса, например.

      If i is the index of some None N then: 
           N's left child is in tree[i*2] 
           N's right child is in tree[(i*2)+1] 

Это двоичное дерево прекрасно работает. Но теперь я хочу поместить в него свойства AVL. Я застрял в этой точке, потому что я не знаю, как сделать вращения в списке. Как вращать, как я могу переместить детей из нового корня? Факт, что они должны сдвигать индексы, не так ли? Кроме того, выполнение этого в списке приводит к тому, что отображение дерева потребует циклического перехода по списку каждый раз, когда я добавляю узел. Это не произойдет в O (logn), больше разрушая всю точку дерева AVL.

Я делаю это в C#. Я просто хочу знать, как эффективно использовать это дерево AVL, используя структуру данных List или любую структуру на основе массива, которая является индексируемой, а не связанным списком. Это важно. Некоторый код для иллюстрации был бы весьма признателен.

Answer 1

Представление дерева в массиве/списке, как вы делаете, является общим для структуры данных кучи, но оно не работает практически для любого другого дерева. В частности, вы не можете сделать это (эффективно) для деревьев AVL, потому что для каждого вращения потребуется слишком много копий.

Answer 2

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

Благодаря ответу Криса, я больше не собираюсь тратить на него время. Я найду другой способ реализовать то, что мне нужно.

Answer 3

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

void shiftUp(int indx, int towards) { 
    if (indx >= size || nodes[indx].key == NULL) { 
     return; 
    } 
    nodes[towards] = nodes[indx]; 
    nodes[indx].key = NULL; 
    shiftUp(lChild(indx), lChild(towards)); 
    shiftUp(rChild(indx), rChild(towards)); 
} 

void shiftDown(int indx, int towards) { 
    if (indx >= size || nodes[indx].key == NULL) { 
     return; 
    } 

    // increase size so we can finish shifting down 
    while (towards >= size) { // while in the case we don't make it big enough 
     enlarge(); 
    } 

    shiftDown(lChild(indx), lChild(towards)); 
    shiftDown(rChild(indx), rChild(towards)); 
    nodes[towards] = nodes[indx]; 
    nodes[indx].key = NULL; 
} 

Как можно видеть, это делается не исследуя рекурсивно каждый поддерево до NULL (определено в этом, как -1) узлы затем скопировать каждый элемент по одному вверх или вниз.

с этим мы можем определить 4 типа вращений, названных по этому Wikipedia Tree_Rebalancing.gif

void rotateRight(int rootIndx) { 
    int pivotIndx = lChild(rootIndx); 

    // shift the roots right subtree down to the right 
    shiftDown(rChild(rootIndx), rChild(rChild(rootIndx))); 
    nodes[rChild(rootIndx)] = nodes[rootIndx]; // move root too 

    // move the pivots right child to the roots right child's left child 
    shiftDown(rChild(pivotIndx), lChild(rChild(rootIndx))); 

    // move the pivot up to the root 
    shiftUp(pivotIndx, rootIndx); 

    // adjust balances of nodes in their new positions 
    nodes[rootIndx].balance--; // old pivot 
    nodes[rChild(rootIndx)].balance = (short)(-nodes[rootIndx].balance); // old root 
} 

void rotateLeft(int rootIndx) { 
    int pivotIndx = rChild(rootIndx); 

    // Shift the roots left subtree down to the left 
    shiftDown(lChild(rootIndx), lChild(lChild(rootIndx))); 
    nodes[lChild(rootIndx)] = nodes[rootIndx]; // move root too 

    // move the pivots left child to the roots left child's right child 
    shiftDown(lChild(pivotIndx), rChild(lChild(rootIndx))); 

    // move the pivot up to the root 
    shiftUp(pivotIndx, rootIndx); 

    // adjust balances of nodes in their new positions 
    nodes[rootIndx].balance++; // old pivot 
    nodes[lChild(rootIndx)].balance = (short)(-nodes[rootIndx].balance); // old root 
} 


// Where rootIndx is the highest point in the rotating tree 
// not the root of the first Left rotation 
void rotateLeftRight(int rootIndx) { 
    int newRootIndx = rChild(lChild(rootIndx)); 

    // shift the root's right subtree down to the right 
    shiftDown(rChild(rootIndx), rChild(rChild(rootIndx))); 
    nodes[rChild(rootIndx)] = nodes[rootIndx]; 

    // move the new roots right child to the roots right child's left child 
    shiftUp(rChild(newRootIndx), lChild(rChild(rootIndx))); 

    // move the new root node into the root node 
    nodes[rootIndx] = nodes[newRootIndx]; 
    nodes[newRootIndx].key = NULL; 

    // shift up to where the new root was, it's left child 
    shiftUp(lChild(newRootIndx), newRootIndx); 

    // adjust balances of nodes in their new positions 
    if (nodes[rootIndx].balance == -1) { // new root 
     nodes[rChild(rootIndx)].balance = 0; // old root 
     nodes[lChild(rootIndx)].balance = 1; // left from old root 
    } else if (nodes[rootIndx].balance == 0) { 
     nodes[rChild(rootIndx)].balance = 0; 
     nodes[lChild(rootIndx)].balance = 0; 
    } else { 
     nodes[rChild(rootIndx)].balance = -1; 
     nodes[lChild(rootIndx)].balance = 0; 
    } 

    nodes[rootIndx].balance = 0; 
} 

// Where rootIndx is the highest point in the rotating tree 
// not the root of the first Left rotation 
void rotateRightLeft(int rootIndx) { 
    int newRootIndx = lChild(rChild(rootIndx)); 

    // shift the root's left subtree down to the left 
    shiftDown(lChild(rootIndx), lChild(lChild(rootIndx))); 
    nodes[lChild(rootIndx)] = nodes[rootIndx]; 

    // move the new roots left child to the roots left child's right child 
    shiftUp(lChild(newRootIndx), rChild(lChild(rootIndx))); 

    // move the new root node into the root node 
    nodes[rootIndx] = nodes[newRootIndx]; 
    nodes[newRootIndx].key = NULL; 

    // shift up to where the new root was it's right child 
    shiftUp(rChild(newRootIndx), newRootIndx); 

    // adjust balances of nodes in their new positions 
    if (nodes[rootIndx].balance == 1) { // new root 
     nodes[lChild(rootIndx)].balance = 0; // old root 
     nodes[rChild(rootIndx)].balance = -1; // right from old root 
    } else if (nodes[rootIndx].balance == 0) { 
     nodes[lChild(rootIndx)].balance = 0; 
     nodes[rChild(rootIndx)].balance = 0; 
    } else { 
     nodes[lChild(rootIndx)].balance = 1; 
     nodes[rChild(rootIndx)].balance = 0; 
    } 

    nodes[rootIndx].balance = 0; 
} 

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

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

int getHeight(int indx) { 
    if (indx >= size || nodes[indx].key == NULL) { 
     return 0; 
    } else { 
     return max(getHeight(lChild(indx)) + 1, getHeight(rChild(indx)) + 1); 
    } 
} 

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

// requires non null node index and a balance factor baised off whitch child of it's parent it is or 0 
private void deleteNode(int i, short balance) { 
    int lChildIndx = lChild(i); 
    int rChildIndx = rChild(i); 

    count--; 
    if (nodes[lChildIndx].key == NULL) { 
     if (nodes[rChildIndx].key == NULL) { 

      // root or leaf 
      nodes[i].key = NULL; 
      if (i != 0) { 
       deleteBalance(parent(i), balance); 
      } 
     } else { 
      shiftUp(rChildIndx, i); 
      deleteBalance(i, 0); 
     } 
    } else if (nodes[rChildIndx].key == NULL) { 
     shiftUp(lChildIndx, i); 
     deleteBalance(i, 0); 
    } else { 
     int successorIndx = rChildIndx; 

     // replace node with smallest child in the right subtree 
     if (nodes[lChild(successorIndx)].key == NULL) { 
      nodes[successorIndx].balance = nodes[i].balance; 
      shiftUp(successorIndx, i); 
      deleteBalance(successorIndx, 1); 
     } else { 
      int tempLeft; 
      while ((tempLeft = lChild(successorIndx)) != NULL) { 
       successorIndx = tempLeft; 
      } 
      nodes[successorIndx].balance = nodes[i].balance; 
      nodes[i] = nodes[successorIndx]; 
      shiftUp(rChild(successorIndx), successorIndx); 
      deleteBalance(parent(successorIndx), -1); 
     } 
    } 
} 

аналогична для вставки это

void insertBalance(int pviotIndx, short balance) { 
    while (pviotIndx != NULL) { 
     balance = (nodes[pviotIndx].balance += balance); 

     if (balance == 0) { 
      return; 
     } else if (balance == 2) { 
      if (nodes[lChild(pviotIndx)].balance == 1) { 
       rotateRight(pviotIndx); 
      } else { 
       rotateLeftRight(pviotIndx); 
      } 
      return; 
     } else if (balance == -2) { 
      if (nodes[rChild(pviotIndx)].balance == -1) { 
       rotateLeft(pviotIndx); 
      } else { 
       rotateRightLeft(pviotIndx); 
      } 
      return; 
     } 

     int p = parent(pviotIndx); 

     if (p != NULL) { 
      balance = lChild(p) == pviotIndx ? (short)1 : (short)-1; 
     } 

     pviotIndx = p; 
    } 
} 

Как вы можете видеть, это просто использует обычные массивы «узел» с, как я перевел его из кода С учетом gitHub array-avl-tree и оптимизациями и балансировка от (ссылка, которую я опубликую в комментарии), но будет работать очень похоже в списке

Наконец, у меня есть минимальное знание деревьев AVL или оптимальных реализаций, поэтому я не знаю 't утверждают, что это ошибка или самая эффективная, но прошли мои предварительные тесты, по крайней мере, для моих целей.