안녕하세요 오유님들

 

프로그래밍을 공부하고 있는 컴공 학부생입니다...

 

이번 과제가 레드블랙 트리를 구축하는 것인데요.

 

일단 이진탐색트리를 먼저 만들고 그 다음에 레드블랙 트리로 발전시켜나가려고하는데

 

이진탐색트리 구현과정에 막히는 부분이 있네요...

 

자식노드와 부모노드가 상호참조하게 하고 싶은데

 

현재 작성한 코드는 부모노드에서 자식노드로 가는 포인터만 존재하고 있습니다...

 

일단 코드 일부분만 올려볼게요.

 

#include <iostream>
#include <string>

using namespace std;

class TreeNode{ // 노드 클래스
 friend class Tree;
public:
 TreeNode( const int &d ) // 노드 생성자. 서브트리를 생성한다.
  : leftPtr( 0 ), data( d ), rightPtr( 0 ) // 자기자신은 입력받은 데이터로 초기화, 왼쪽 자식과 오른쪽 자식 생성
 {
  
 }
private:
 TreeNode *leftPtr; // 왼쪽 자식 포인터
 TreeNode *rightPtr; // 오른쪽 자식 포인터
 TreeNode *parPtr; // 부모 포인터
 int data; // 노드에 들어갈 데이터
 //int maxheight;

 enum { red, black } color;
};

class Tree{ // 트리 클래스
public:
 Tree(); // 트리 생성자
 void insertNode( const int & ); // 입력 함수. insertNodeHelper를 호출한다.
 void inOrderTraversal() const; // 중위순회 함수. inOrderHelper를 호출한다.
 void SearchNode( const int & ); // 탐색 함수. SearchNodeHelper를 호출한다.
 //void TestHeight();
private:
 TreeNode *rootPtr; // 루트 노드 포인터

 void insertNodeHelper( TreeNode **, const int & ); // 입력 함수
 void inOrderHelper( TreeNode * ) const; // 중위순회 함수
 void SearchNodeHelper( TreeNode *, const int & ); // 탐색 함수

 void reColoring();
 void reStructuring();

 //높이 함수
 //void HeightHelper( TreeNode *, int &, int &, int & );

 void AVLstructuring();
 
};

Tree::Tree(){ // 트리를 생성함과 동시에 루트노드의 포인터를 0(External) 으로 초기화 한다.
 rootPtr = 0;
}

void Tree::insertNode( const int &value ){ // 입력 함수. main에서 데이터를 받아온다.
 insertNodeHelper( &rootPtr, value );
}

void Tree::insertNodeHelper( TreeNode **ptr, const int &value ){
 if ( *ptr == 0 ){ // 현재 가리키고 있는 노드가 External 노드이면 새로운 노드를 하나 생성한다.
  *ptr = new TreeNode( value ); // 노드 생성시 main에서 입력 받은 데이터로 초기화한다.
  // 부모노드의 주소를 현재 노드의 parPtr에 저장해야함.
  cout << value << " 가 입력되었습니다." << endl;
 }
 else{ // 현재 가리키고 있는 노드가 internal 노드일 때 External 노드를 찾아간다.
  if ( value < (*ptr)->data ){ // 입력받은 값이 현재 노드의 데이터 값보다 작으면 왼쪽 노드를 확인한다.
   insertNodeHelper( &((*ptr)->leftPtr), value );
  }
  else{ // 입력받은 값이 현재 노드의 데이터 값보다 크면 오른쪽 노드를 확인한다.
   if ( value > (*ptr)->data ){
    insertNodeHelper( &((*ptr)->rightPtr), value );
   }
   else // 입력 받은 값이 이미 트리에 있으면 메세지 출력
    cout << value << "는 이미 존재하는 값입니다." << endl;
  }
 }
}

이게 코드 일부분이고 주요한 부분은 빨간색으로 색칠해놨어요.

 

제멋대로 코드라서 해석하기 힘드실 것같네요...

 

그래도 과제여서 혼자 힘으로 해보려고했는데 도저히 저부분에서 막혀서 진도가 나가지 않아서

 

조언좀 얻고자 이렇게 도움을 청해봅니다...

 

프로그래밍 고수님들의 조언 부탁드립니다ㅠㅠ