는 목록을 사용하여 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 트리 기능을 추가하려고합니다. 나는 목록에 회전을 만드는 방법을 모르기 때문에이 시점에서 붙어 있습니다. 교대로 새로운 루트의 자식들을 어떻게 움직일 수 있습니까? 사실 그들이 인덱스를 이동해야합니까? 또한 목록에서이 작업을 수행하면 트리를 표시 할 때마다 노드를 추가 할 때마다 목록을 반복해야합니다. 이것은 AVL 트리 전체를 파괴하는 O (logn)에서 발생하지 않을 것입니다.

저는 C#에서 이것을하고 있습니다. 이 AVL 트리를 효율적으로 List 또는 배열 기반 데이터 구조 thats를 사용하여 효율적으로 만드는 방법을 알고 싶습니다. 이것은 중요합니다. 설명 할 수있는 코드는 크게 감사 할 것입니다.

Answer 1

배열/목록에서 트리를 나타내는 것은 힙 데이터 구조에서 일반적이지만 다른 종류의 트리에서는 작동하지 않습니다. 특히, 각 회전에는 너무 많은 복사가 필요하기 때문에 AVL 트리에 대해 (효율적으로)이 작업을 수행 할 수 없습니다.

Answer 2

우리는 malloc을 사용할 수없는 임베디드 응용 프로그램에이 기능이 필요했습니다. 할 수 있다면 시도하기 전에 어떤 종류의 데이터 구조 알고리즘 구현도 완료하지 않았 으면합니다. 코드를 작성하는 동안 많은 것들을 움직여야한다는 것을 깨달았습니다. 나는 치료법을 찾고이 게시물에 올랐다.

Chris의 답변 덕분에 더 이상 시간을 낭비하지 않을 것입니다. 나는 내가 필요한 것을 구현할 다른 방법을 찾을 것이다.

Answer 3

나는 대답을 찾았다 고 믿는다. 속임수는 목록을 위아래로 이동하여 회전하는 동안 유효한 노드를 덮어 쓰지 않도록한다.

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; 
} 

당신이 다음 각 요소까지 하나 아래 하나 복사 노드들이이 (-1로이 정의)이 NULL 때까지 반복적으로 각 서브 트리를 탐색하여 수행됩니다 볼 수 있듯이. 이와

우리는 노드를 덮어 쓰게 이동하는 경우에 우리가 균형을 저장하는 단일 노드 효율로

를 복사하는 것이이 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; 
} 

참고 따라 이름이 회전의 4 가지 유형을 정의 할 수 있습니다 각 노드의 높이 차이를 얻는 것이 필요합니다.

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); 
     } 
    } 
} 

유사하다 내가 gitHub array-avl-tree 및 최적화 주어진 C 코드에서 번역 당신이 그냥 "노드"의의 일반 배열을 사용하여 볼 수 있듯이 삽입이

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; 
    } 
} 

입니다 (코멘트에 올릴 링크)에서 균형을 잡을 수 있지만 목록에서는 꽤 비슷하게 작동합니다.

마지막으로 AVL 트리 또는 최적의 구현에 대한 지식이 거의 없습니다. 이것은 버그가 없거나 가장 효율적이라고 주장하지만 최소한 내 목적을 위해 예비 테스트를 통과했습니다.