[자료구조] Binary Search Tree c++ 구현 [컴공과고씨]

트리

트리는 사이클이 없는 연결 그래프로 각 노드가 하나의 부모 노드와 간선으로 연결되어있는 구조이다.

많은 트리가 있는데 그중 binary search tree에 대해서 알아보자.

 

일단 트리에 구조를 보면

이런 식으로 되어있다.

자신보다 바로 위에 있는 노드를 부모 노드 parent node 라 하고 그 아래에 있는 노드를 child node라고 한다.

맨 위의 노드를 root node라 하고 

이 곳부터 level 0 이고 그 밑에 줄이 level 1 이런식으로 내려간다. 지금 예는 level 2 트리인 것이다.

leaf node는 노드가 없는 노드를 말합니다. 

ancestor(조상)은 부모 노드로만 이동해서 갈 수 있는 노드들이고

descendent(자손)은 자식 노드로만 이동해서 갈 수 있는 노드들입니다.

subtree(서브트리)는 어떤 노드가 부모 노드 간의 연결을 끊었을 때 만들어지는 새로운 트리를 말합니다.

 

Binary Search Tree는 원소의 중복을 허용하지 않고, 왼쪽 서브 트리는 자기보다 작은 값을, 오른쪽 서브트리는 자기보다 큰 값을 저장하는 특징이 있습니다.

 

binary search tree

동적할당 방식으로 구현을 했습니다.

 

Insert(삽입)

- 왼쪽은 작은 값, 오른쪽은 큰 값 즉, 값을 비교하면서 쭉쭉 들어가다가 NULL이 되면 노드를 삽입해주면 된다.

이때 중요한 것이 재귀로 구현을 할건데 2가지 방법으로 나뉜다. 

래퍼런스 타입을 사용하는 것과 return 값을 주어 마지막에 노드가 전부 이어지도록 하는 방법이 있다.

 

Delete(삭제)

- 삭제 같은 부분은 삭제할 노드를 찾고 그 노드에 다른 대체할 노드를 찾아주는 것입니다.

1. 두 자식 모두 있는 경우

트리는 트리의 구조를 유지해야하고 그래서 왼쪽 서브 트리는 조상 노드보다 작은 값들이고 오른쪽 서브 트리는 큰 값들 입니다. 그래서 삭제할 노드 기준으로 왼쪽 서브트리에서 가장 큰 값과 바꾸어 주거나 오른쪽 서브 트리에서 가장 작은 값과 위치를 바꾸어주고  삭제를 해주면 됩니다.

 

2. 한쪽 자식이 없는 경우 

왼쪽 자식이 없는 경우는 오른쪽 서브트리를 붙여주면된다.

오른쪽 자식이 없는 경우는 왼쪽 서브트리를 붙여주면된다.

 

 

트리의 순회

1) pre-order(전위 순회)

 cout -> 왼쪽 -> 오른쪽

2) in-order(중위 순회)

 왼쪽 -> cout -> 오른쪽

3) post-order(후위 순회)

 왼쪽 -> 오른쪽 -> cout

 

cout은 쉽게 이해하기 위해서 적어놓은 것이고 저건 자신을 방문한다고 보면 됩니다.

이게 무슨 말이나면 트리를 순회할 때 순서로 새로운 노드로 갈 때 마다 저 사이클을 반복한다고 보시면 됩니다.

in-order로 예를 들면 왼쪽 노드로 감 -> 새로운 노드에서 또 왼쪽 .. 계속 왼쪽가다가  null을 만나면 이제 cout (자신노드)

그 후 오른쪽으로 감 만약 오른쪽에 또 노드가 있다면 다시 새로운 노드로 왔기 때문에 왼쪽으로 가는 사이클 반복 이런식으로 된다. 이 부분은 코드로 보면 이해하기 편하다.

 

 

Destroy

트리를 전부 삭제하는 것으로 중요한 것은 동적할당을 해주었기 때문에 메모리 해제 부분을 당담한다.

 

나머지 함수 부분은 코드를 보면서 이해하는 것이 편할 것이다.

* 참고서적 c++ plus data structures

* 코드는 https://github.com/goragoraki/Data-Structure 에서 볼 수 있습니다.