트리, 이진 트리 Binary Search tree

트리와 이진 트리 , Binary Search Tree 구조와, 방식에 대해서 이해해보자

 

- 트리

일반적으로 계층 구조의 자료구조를 표현할때 사용하는 구조이다.

자식-부모 간의 관계로 되어있고, 싸이클 구조를 가지지 않는다.

 

 

되게 간단하다. 단순 트리 구조는, 동료 노드와, 부모 자식 노드 그리고 최상단의 루트 노드가 존재한다는 것이 전부이다.

 

이진트리

- 자신의 하위 노드의 차수가 최대 2인, 트리 구조를 의미한다.

부모-자식간의 노드 구조는 동일하고, 자식을 최대 2개가진다고 이해하면 된다.

 

이진트리는 종류가 조금 씩 있는데, 

1. 완전 이진 트리

2. 전 이진 트리

3. 포화 이진 트리

 

이렇게 3가지의 트리가 존재한다.

 

1. 완전 이진 트리

완전 이진 트리는 , 왼쪽에서 오른쪽으로 데이터가 채워진다는 것을 순서대로 잘 지켰냐, 지키지 않았냐 이다.

위의 사진 대로라면, 완전 이진트리인 경우에는, 20 하위에 15가 , 왼쪽에 채워져있기 때문에, 그리고 오른쪽은, 30이 오른쪽으로 채워져있기 때문에, 완전 이진 트리가 아니다.

 

새로운 데이터의 노드가 채워진다고 가정하면, 완전 이진트리의 경우, 다음에 채워지는 노드가 오른쪽이 되기 때문에 잘 맞게 들어가지만

완전 이진 트리가 아닌 경우에는 왼쪽에 차있는 걸 패스하고 새로운 노드를 생성하고, 하위에들어가야 하므로, 완전 이진트리가 되지 않는다.

 

2. 전 이진트리

전 이진트리는 간단하다, 모든 노드의 하위 노드가 0개 또는 2개인 경우에 해당된다.

 

하위 자식 노드가 있다면, 무조건 2개 아니라면, 0개일때 해당 전 이진 트리에 해당된다.

 

이런 이진트리에 대한 탐색을 하는 방법은 몇가지 방법이 있다.

우선순위에 대한 산정을 다르게 하여, 다음 탐색 노드에 대한 선택을 다르게 하는 것이다.

 

이런 이진 노드가 있다고 가정하자

 

1. 중위 순회

왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 탐색한다.

루트를 중간의 우선순위에 두고, 탐색을 한다.

 

해당 위의 노드를 탐색하는 순서는, 중위 순회라는 가정하에는

4 - 2 - 5 - 1 - 3 순으로 탐색한다.

 

2. 후위 순회

왼쪽 서브트리 , 오른쪽 서브트리, 루트 순으로 탐색한다.

4 -2 - 5 - 3 - 1

순으로 탐색이 된다.

 

3. 전위 순회

루트가 제일 앞으로,  1- 2 - 4 -5 -3 순으로 탐색이 된다.

 

이진 탐색 트리 (Binary Serach Tree)

모든 키값의 왼쪽 노드에는 자신보다 작은 값이, 오른쪽 노드에는 자신보다 큰값의 규칙을 지키는 트리 구조이다.

해당 트리 구조의 규칙은, 모든 노드는 유일한 값을 가진다라는 규칙이 있다.

 

다만 단점은, 한쪽의 노드에만 값이 몰려서 저장되는 편향 트리의 구조가 될 수 있다는 단점이 있다.

이를 보완하기 위해, 균형 잡힌 이진 탐색 트리, 레드 블랙 트리와 AVL 트리가 고안 되었다.

 

1. 레드 블랙 트리

- 자가 균형 이진 탐색 트리라고도 불리며, 연관 배열을 사용하는 구조이다.

편향 구조의 이진트리가 되는 것을 방지하는 조건을 추가한다. 삽입,삭제에 대한 시간이 동일하며, 최악의 경우에도 동일한 수행시간을 가진다.

 

레드 블랙 트리의 두가지는, restructing과 recoloring 이 존재한다.

restructing 은 구조를 다시 짜는 것인데, 값이 새로 추가되면, 더블 red를 판별해서 부모 ~ 자식 까지의 값을 오름차순으로 정렬하고

가운데 값을 부모, 검정으로 변경하고, 자식을 모두 red로 변경하는 작업이다.

 

이 그래프의 상태에서 6이라는 값이 들어왔다고 가정해보자

해당 그래프에서, 4-7-6을 가지고 있다면, 정렬을 해서, 4-6-7로 만든다.

이때 가운데 값인 6을 부모로 만들고, 검정으로 변경한다. 후에, 하위 4,7을 자식 빨간색으로 변경하여, Double red를 회피하면서

편향 이진 트리가 될 가능성을 배제 해준다.

 

만약의 새로 짠 트리 구조에서, 어떤 값이 들어온다면, 한쪽으로 편향되지 않고, 새로운 값이  restructing 된 트리로 들어오기 떄문에,

한쪽으로 편향되지 않고 균형 잡힌 트리 구조를 이어나갈수 있게 해준다.

 

 

AVL 트리구조는 어떻게, 편향 이진 탐색 트리가 되는 것을 방지해줄까?

바로 BF를 사용하는 것이다. Balanced Factor라는 의미로도 쓰이고, 해당 BF를 사용해서, 편향 이진 트리가 되는 것을 방지해준다.

 

BF 계산식은 , 각 노드 별로, BF를 가지고 있고, 해당 계산식은, 왼쪽 노드 높이 - 오른쪽 노드 높이이다.

 

이런식으로, 편향 된 구조를 가지게 되면, BF는 계산되어서, 각 해당 값으로 BF를 가지고 있게 된다.

해당 3의 삽입 시점에서, 위 루트로 올라가면서 만나는 처음의 BF불균형을 바로 잡는 것이. AVL의 트리구조의 핵심이다.

해당 값으로 잡고, 트리에 대한 재 정렬을 한다.

 

 

해당 케이스는 5를 삽입 했을 경우이다.

삽입 시점에 루트의 불균형은 12와 3에서 발생하게 되고, 해당 불균형을 바로 잡기 위해서,

3, 12, 5를 가지고 정렬 및 3,5,12 로 다시 균형 잡힌 트리의 구조로 바꿔준다.

 

 

해당 방식으로, 균현 잡힌 이진탐색 트리를 가지게 할수 있다.

 

이진 탐색 트리는, 단순하게 보면 노드보다, 작은값을 왼쪽 큰값을 오른쪽으로 정렬하는 자료구조이지만,

편향 이진 탐색 트리가 되는 것을 방지하게 하기 위해서, AVL이나, 레드 블랙 트리구조를 사용한다는 것을 알아 두어야 한다.