바이너리 검색 트리에 가장 적합한 루트 찾기

Question

내 바이너리 검색 트리에 가장 적합한 루트를 찾으려고합니다. 즉 이것은 내 이진 검색 트리입니다.

  42 
    / \ 
    / \ 
    25  53 
    /\ /\ 
    23 41 49 55 
/\/\/\/\ 

그런 다음 배열로 inOrder walk 형태로 저장합니다.

| 23 | 25 | 41 | 42 | 49 | 53 | 55 | .........
........... ↑ ........... ↑ ........... ↑. ..........

그래서 화살표를 가리키는 노드는 어느 것이 가장 좋은 루트 41, 42, 53인지 알아 내려고하는 노드입니다. (배열이 더 크고 아프다. 트리의 주어진 깊이로 배열의 홀수 색인). 나는 나무가 이미 균형을 이루고 있을지도 모른다는 것을 알고있다. 그러나 이것은 실험이다.

그래서 나는 새로운 루트로서 모든 홀수 색인을 시도하고 이전 높이와 각 높이를 비교해야하며 어느 것이 내 최고의 높이인지 결정할 수 있어야합니다. 즉, 내가 확인하고 배열의 이전 노드와 높이를 비교해 각각 그래서이

  25       25 
      \        \ 
      \        \ 
      42   or     53 
       \       /
       53       42 
        \      /

같은 트리를 가질 수 있습니다 나의 새로운 루트 25 내가 결정한다면 나는 그것이 나에게 줄 것이다 노드를 반환 최고의 노드. 이상적인 루트를 삽입 할 수있는 숫자의 중간입니다 : 당신은 꽤 간단하다 루트 노드를 찾는 정렬 된 순서로 숫자로 시작하고 이후

void rebalance(){ 

    //this is the size for the array and NumDepth is defined at the constructor 

    int size = (pow (2,(numDepth +1))-1); 
    Node* Array2 [size]; 
    int i = 0; 
    int bestH = 0; 
    Node* temp; 

    for (int i=0; i < size; i++){ 
      Array2[i]= new Node(); 
      Array2[i]= NULL; 
    } 
    //this function will be the one creates the inOrder walk and saves my nodes inside the array 
    storeInOrder(rootBST, Array2, i, numDepth); 

    temp = shortestBST(Array, rootBST, bestH, height); 


} 

Node* shortestBST(Node *root[], Node* root, int &bestHeigth, int sizeA) { 
//root is my main tree basically 

//this is how i know that i have to use the odd numbers in the array 

    for(int i= 1; i< sizeA; i+=2){ 

     //inside here I am supposed to do a recursion to check every node inside the array to check the node that is the best 
     //they gave me a hint saying that i can point the nodes in the array to the ones in my main tree to create the tree with the new testing root in order to check if that node can create a best tree but i don't know how to do that using recursion 
//each of my nodes hold a key, a height and a size of a subtree , left to point to the left and a right to point to the right 

    } 




} 

Node::Node() { 

    sizeSub=0; 
    height=1; 
    key=0; 
    left=NULL; 
    right=NULL; 
} 

Answer 1

비슷한 질문 그냥 뭐 여기의 요청을 받고있는 것처럼 보이는 알고리즘있다 : 마우스 오른쪽 회전 동작을 사용

1. 는, 연결리스트 (일명 백본 또는 포도 나무)
에 나무를 돌립니다
2. 백본을 완벽하게 균형 잡힌 BST로 바꾸려면 백본의 모든 두 번째 노드를 부모에 대해 순환시킵니다.

http://www.geekviewpoint.com/java/bst/dsw_algorithm

Answer 2

: 지금까지 나는이 시도.

이렇게하면 삽입을 재귀 적으로 수행하는 것이 간단합니다. 중앙값을 찾아 루트로 삽입 한 다음 왼쪽 하위 배열을 왼쪽 하위로 삽입하고 오른쪽 하위 배열을 오른쪽 하위로 삽입하십시오.