[알고리즘] C 트리(삽입, 검색, 삭제)

오늘은 트리의 삽입, 검색, 삭제에 대한 코드를 작성해보려고 한다.

간단한 UI를 만들어 구현을 해보겠다.

 

보이는 출력은 레벨 순회를 통하여 출력해보겠다.

레벨 순회를 위한 include<queue>와 c++의 stl 사용을 위해 using namepsace std; 를 추가해준다.

 

구조체 만들기

값을 담을 int형 data와 자기 참조 구조체인 노드 *left, *right를 만든다. 

 

 

동적 할당과 실질적인 값을 받기 위한 alloc_new_node 함수 만들기

새로운 new_node 구조체 변수를 만들어 매개 변수로 받는 값을 대입 후 return 해준다.

 

 

삽입 함수

new_node 함수에서 node와 node에 입력할 값을 받아온다.

node가 존재하지 않는다면 alloc_new_node를 통해 값을 대입한다.

node가 존재한다면 node의 data와 입력받은 value 값을 비교한다.

node의 data가 크다면 node의 왼쪽 자식 노드와 value 값을 재귀 함수로 호출한다.

node의 data가 작다면 node의 오른쪽 자식 노드와 value 값을 재귀 함수로 호출한다.

두 가지 경우, 재귀 함수를 돌다 node가 null인 조건문을 만족하게 되고 alloc_new_node 함수를 호출하게 된다.

 

 

노드 생성 시 값을 입력할 함수 만들기

while문을 돌면서 input으로 값을 입력 받고 insert_node 함수를 통하여

노드를 생성 후 node를 while문 종료 시 node를 return 한다.

 

 

 

검색 함수

탐색 알고리즘에는 두 가지 방법이 존재한다.

순환적(재귀) 탐색, 반복적 탐색이 있는데 이번에는 반복적 탐색을 만들었다.

탐색할 노드를 입력 받아 순회를 한다.

while문을 통하여 node가 null이 될 때까지 순회를 하는데 node가 null이 된다면 찾는 노드가 존재하지 않는다는 뜻이다.

node의 data와 입력 받은 value를 비교하여 같다면 출력 후 node를 return 한다.

node의 data가 value 보다 크다면 node에 node의 left를 대입하여 다시 반복한다.

node의 data가 value 보다 작다면 node에 node의 right를 대입하여 다시 반복한다.

 

 

레벨 순회

queue를 이용하여 레벨 순회 함수를 만들었다.

q에 root를 push 후 q가 비어 있을 때까지 while문을 돈다.

 

 

 

삭제 함수는 조금 어려울 수 있지만 방향을 생각하여 함수를 따라 간다면 이해할 수 있을 것이다.

삭제에는 여러 가지 경우가 존재한다.

1. 왼쪽, 오른쪽 자식 노드가 null인 경우

2. 왼쪽은 존재하지만 오른쪽 자식 노드가 null인 경우

3. 왼쪽은 null이지만 오른쪽 자식 노드가 존재하는 경우

4. 둘 다 존재하는 경우 

 

삭제 함수

우선 root의 data와 삭제하고자 하는 value가 같을 때까지 재귀 호출을 한다.

이제 값이 같을 때 (1)번의 경우 자식 노드가 존재 하지 않기 때문에 root 를 free 시켜주면 끝난다.

(2)번은 왼쪽 자식 노드는 없지만 오른쪽 자식 노드는 존재 하기 때문에 temp 라는 변수를 만들어

오른쪽 자식 노드를 담고 return 시킨다. (3)번도 (2)번과 동일하다.

(4)번은 자식 노드가 둘 다 존재할 경우인데 이제 여기서 생각 해야 할 부분이 있다.

root 노드의 왼쪽 자식 노드에서 가장 큰 수를 root로 변환 시킬 것인지

root 노드의 오른쪽 자식 노드에서 가장 작은 수를 root로 변환 시킬 것인지를 결정 해야 한다.

이번에는 root의 오른쪽 자식 노드에서 가장 작은 수를 가져오는 함수를 만들었다.

 

find_connect_node라는 함수에 root의 right를 root로 받아 cur에 대입 후

cur의 left가 null이 될 때까지 이동 시킨 뒤 return 한다.

이 때 return되는 cur의 값은 root보다 크고 root의 오른쪽 자식 노드 중에서 가장 작은 수이다.

 

 

삭제할 값을 입력하는 함수

while문을 돌면서 value 값을 입력 받고 delete_nde 함수를 통하여

노드를 삭제한다. while문이 끝나면 node를 return 한다.

 

 

Main 함수

삽입, 검색, 삭제까지 할 수 있는 main을 만들었다.