이진 탐색 트리 특징, 노드삽입, 구현

 

 

 

 

●이진탐색트리(Binary Search Tree : BST)

 

-부모를 기준으로 왼쪽에 있는 노드들은 모두 부모보다 작은 데이터, 오른쪽은 부모보다 큰 데이터.

ex) 22를 기준으로 왼쪽은 모두 22보다 작은 데이터, 오른쪽은 22보다 큰 데이터

 

-작으면 왼쪽, 크면 오른쪽에 위치하기 때문에 중복 데이터는 허용되지 않는다.

 

 

●노드삽입 방법

-루트부터 비교하면서 내려온다. 말단까지.

ex) 8번노드 삽입하는 과정.

8은 22보다 작으니 왼쪽으로,

15보다 작으니 왼쪽으로,

7보다 크니 오른쪽으로,

10보다 작으니 왼쪽으로 가는데 10왼쪽 자리가 없다.

그래서 10의 왼쪽자리에 자식노드로 삽입이 된다.

 

 

 

●이진탐색트리 삽입을 코드로 구현

 

 

완성된 코드

typedef struct TREE {
  int value;
  struct TREE* left;
  struct TREE* right;
} TREE;

TREE* addNode(TREE* t, int data) {
  if (!t) {
    t = (TREE*)malloc(sizeof(TREE));
    t->value = data;
    t->left = NULL;
    t->right = NULL;
  }
  else if (data < t->value)
    t->left = addNode(t->left, data);
  else if (data > t->value)
    t->right = addNode(t->right, data);
  return t;
}

 

 

먼저 루트의 주소부터 비교하며 내려간다.

그래서 인수로 루트값과 삽입하려는 데이터 값을 전달을 받는다.

ex) 위 그림에서 5번노드를 삽입하고 싶다면 (8번노드 주소, 데이터 5) 이렇게 전달받는 것이다.

TREE* addNode(TREE* t, int data)

 

 

 

그 다음 일단 t가 NULL인지 물어본다.

t는 8번을 가리킨다.

NULL이 아니므로 다음 조건으로 이동한다.

if (!t)

 

 

 

삽입하려는 데이터 값이 t보다 작은지, 큰지 물어본다.

t보다 작으면 왼쪽으로, 크면 오른쪽으로 가기 때문이다.

else if (data < t->value)

else if (data > t->value)

 

 

 

5번(삽입하려는 값)은 8번(t)보다 작기 때문에 (data <  t->value) 를 만족한다.

그래서 왼쪽으로 이동한다.

왼쪽으로 이동하려면 4번노드의 주소값으로 이동해야하기 때문에 t->left 주소값을 가지고 다시 재귀호출을 한다.

else if (data < t->value)
  t->left = addNode(t->left, data);

 

 

 

그러면 두번째 호출했을 때 t는 4번노드가 된다.

즉, 아래 코드에서 t는 원래 8번노드에서 4번노드가 된다는 것이다.

TREE* addNode(TREE* t, int data) {
  else if (data < t->value)
    t->left = addNode(t->left, data);
}

 

 

 

그 다음 5번은 4번보다 크기 때문에 그 아래 조건으로 가게 된다.

그래서 t->right에 의해 오른쪽으로 가기 때문에 t는 7번노드의 주소를 가지며 다시 재귀호출하게 된다.

else if (data > t->value)
  t->right = addNode(t->right, data);

 

 

 

현재 t는 7번이기 때문에 5는 7보다 작아서 왼쪽으로 가게 된다.

t는 7의 왼쪽이 되기 때문에 왼쪽으로 가면 NULL이 된다.

else if (data < t->value)
  t->left = addNode(t->left, data);

 

 

 

이제 t가 NULL이므로 메모리 할당으로 5번노드를 만든다.

그리고 return t 하게되면 호출했던 함수로 돌아가기 때문에 7번으로 돌아간다.

결과적으로 7번 주소와 연결되어서 삽입할 수 있게 된다.

if (!t) {
  t = (TREE*)malloc(sizeof(TREE));
  t->value = data;
  t->left = NULL;
  t->right = NULL;
}

 

 

 

이러한 방식으로 노드를 삽입할 수 있다.