Tree Traversal - Pre-Order, In-Order, Post-Order(feat.이진 탐색 트리(binary search tree)

우선, binary search tree에 대해서 알아 보겠다. 

우선 난 여태까지 대단한 착각을 하고 있었다. 

Binary Search(이진 탐색)과 Binary Search Tree(이진 탐색 트리)의 차이점에 대해서 별로 생각해 보지 않아서,

두 개 모두 같은 것이라고 보고,Binary Search Tree도 Binary Search(이진 탐색)과 같은 방식으로 동작하는 줄 알았다.

 

이진 탐색(Binary Search) vs 이진 탐색 트리(Binary Search Tree)

이진 탐색(Binary Search) 

1. 중복된 값을 허용한다. (왼족 자식 노드는 부모 노드와 같거나 작고, 오른쪽 자식 노드는 부모 노드보다 크다 )

2. 배열의 mid_index를 기점으로 탐색값과의 대소관계를 이용하여 범위를 좁혀 나간다. 

이진 탐색 트리(Binary Search Tree)

1. 중복된 값을 허용하지 않는다( 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 크다 )

2. 이진 탐색(Binary Search)과 같이 배열로 구현되지 않고, 실제 Tree 형태로 구현을 한다.(이진 탐색도 사실 Tree도 구현이 가능하긴 하다)

 

트리의 순회(traversal)(feat. inOrder,PreOrder,PostOrder - traversal) with 이진 탐색 트리

1. In-Order Traversal(중위 순회) : 이진 탐색 트리를 중위 순회하면, 오름차순 크기로 정렬이 가능하다

-> 연산식(ex 3+5 ) 등을 이진 트리로 구현하여 중위 순회를 이용하여 연산식을 복원하기도 한다. 

 

 

전위 순회

후위 순회

 

이진 탐색 트리(Binary Search Tree)의 삽입/삭제/조회

-> 삽입/조회는 간단하니, 여기서는 상대적으로 복잡한 삭제의 동작 방식에 대해서 자세히 다루겠다. 

삭제의 3가지 경우의 수

1. 삭제 대상의 노드에 자식 노드가 0개인 경우

-> 처리가 가장 간단한 경우이다.

 

2. 삭제 대상의 노드에 자식 노드가 1개인 경우

 

3. 삭제 대상의 노드에 자식 노드가 2개인 경우

-> 아래 예시는 루트 노드를 삭제하는 예시이나, 루트 노드가 아니더라도 자녀 노드가 2개인 노드의 처리는 같다. 

keyPoint : 선임자(precessor) or 후임자(successor) 중 하나를 삭제된 노드 위치(예시에서는 루트 자리)로 이동시켜서 이진

탐색 트리의 규칙에 맞게 트리를 재정렬한다. ( 이 예제에서는 후임자를 올리도록 하였다 )

 

 

delete(50) 완성

 

이진 탐색 트리의 Time Complexity : O(N)

편향 이진 트리( degenerate binary Search )일 때, 삽입/삭제/조회에 있어서 최악의 time complexity를 가진다.

최악의 경우에는, 모~~~든 노드들을 방문해야 할 가능성이 있으므로 0(N)이다. 

최선의 time complexity 또한 편향 이진 트리에서 일어나며, 

위와 같은 왼쪽 편한 이진 트리라면, 루트 노드 90 보다 큰 key값의 삽입/조회, 그리고 루트 노드 90의 삭제 시에 일어 나며

그 time complexity는 O(1)이다. 

 

이진 탐색 트리의 장점 

1. 삽입/삭제가 용이하다.

2. 중위 순회를 이용하면 값을 순서대로 방문(오름차순 방문)이 가능하다. 

이진 탐색 트리의 단점 

편향 이진 탐색 트리의 경우, 최악의 경우, 모~~든 노드들을 다 방문해야 하므로 시간 복잡도가 o(N)으로 성능이 안 좋아 진

다. 

-> 이러한 이진 탐색 트리의 단점을 극복하기 위하여, AVL 트리, Red-Black 트리 등이 등장함.