배열 BST의 삽입 정렬은 어떻게 작동합니까?

Question

나는 그것을 재귀 적으로 시도했다. 부모 정수인 varaible은 2*i +1이 leftChild이고 오른쪽이 2*i +2 인 공식과 일치한다.

void BST::insert(const data &aData) 
{ 
    if (items[Parent].empty) 
    { 
     items[Parent].theData = aData; 
     items[Parent].empty = false; 
    } 
    else if (aData < items[Parent].theData) 
    { 
     Parent = 2 * Parent + 1; 
     if (Parent >= maxSize) this->reallocate(); 
     this->insert(aData); 
    } 
    else 
    { 
     Parent = (2 * rightChild++)+ 2; 
     if (Parent >= maxSize) this->reallocate(); 
     this->insert(aData); 
    } 
} 

원래 부모보다 작은 항목 ... 를 삽입 할 때 그것은 잘 작동하지만 난 뭔가를 찾을 때가 모든 나사 그것을 큰 : X 여기

void BST::reallocate() 
{ 
    item *new_array = new item[maxSize*2]; 

    for (int array_index = 0; array_index < maxSize; array_index++) 
    { 
     if (! items[array_index].empty) 
     { 
      new_array[array_index].theData = items[array_index].theData; 
     } 
    } 
    maxSize *= 2; 
    delete [] items; 

    items = NULL; 
    items = new_array; 
} 

내 ctor에 이렇게이다 아무도 내가 다음 더 이상 혼란을 얻을 수 없습니다 :

BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0), 
leftChild(0), rightChild(0) 
{ 
    items->empty = true; 
    maxSize = capacity; 
} 
private: 
    int size; // size of the ever growing/expanding tree :) 
    int Parent; 
    int maxSize;  
    int leftChild; 
    int rightChild; 
    struct item 
    { 
     bool empty; 
     data theData; 
    }; 
    item *items; // The tree array 

위의 삽입 기능은 .. 사실은 내가이 얻을 수있는 최선

        R 
           /\ 
          / \ 
          / \ 
          L  X 
          /\ /\ 
          J V K T <--The only out of place node. 
         /\ \ 
         /NULL \ 
         G  /
           P 

삽입 할 때 : R, L, J, G, X, K, V, P, T를 나는 당신의 문제를 의심 할

Answer 1

이 라인에 순서대로 :

Parent = (2 * rightChild++)+ 2; 

왜 대신 (2 * Parent) + 2의 여기 rightChild를 사용하고 있습니까? 당신은 또한 할 수 있습니다

inline int getLeftChildIndex(int nodeNdx) { return (nodeNdx * 2) + 1; } 
inline int getRightChildIndex(int nodeNdx) { ... } 
inline int getParentIndex(int nodeNdx) { ... } 

:

인덱스 주어, 당신은 왼쪽/오른쪽 어린이와 부모의 인덱스를 계산하기위한 클래스에 몇 가지 간단한 인라인 함수를 추가 할 수 있습니다 상황이 명확하게하려면 새 노드를 삽입 할 위치를 결정하려면 search() 또는 find() 메서드를 사용하는 것을 고려해야합니다 (하나 있다고 가정합니다). 검색 함수는 기존 노드의 인덱스를 반환해야합니다 (중복 값의 삽입을 처리하는 방법은 사용자에게 달려 있음) 또는 새 값을 삽입해야하는 위치의 인덱스를 반환해야합니다.