이진트리 ADT

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

이진트리 ADT

모든 노드의 차수가 2 이하인 트리.

이진트리 ADT를 구현화하면 자료구조로 간주한다.

이진트리의 상태 & 종류

• Rooted Binary-Tree  (루트 이진트리)

루트 노드만 존재하는 이진트리.

• Full/Strictly Binary-Tree  (정 이진트리)

모든 노드의 차수가 0 또는 2.

• Complete Binary-Tree  (완전 이진트리)

트리의 높이 - 1 레벨까지는 꽉찬 트리.

단, 마지막 레벨의 노드는 좌측부터 채워져 있어야 한다.

• Perfect Binary Tree  (포화 이진트리)

마지막 레벨까지 꽉찬 트리.

+ PS,

영문 위키도 그렇고,  이진트리의 상태와 종류에 대한 의견이 제각각이다.

어떤 곳에서는 Full == Perfect 이라고 설명한 사이트도 있었다.

이 포스트를 작성하는데 참고한 리소스를 밝힌다.

http://ddmix.blogspot.com/2016/03/binary-tree-errata.html

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

이진트리 ADT의 구현

• 배열?

루트 노드를 1로 두고 시작.

자신의 인덱스 번호를 k라고 하면,  자식의 인덱스 번호는 2*k, 2*k+1.

• 연결 리스트?

2개의 포인터를 가진 노드를 사용하여 트리를 표현.

메모리 사용량은 노드의 개수에 비례.

이진검색을 위한 정렬유지

트리의 구조로부터 이진검색을 활용할 수 있다.

현재 노드의 값을 기반으로 작으면 왼쪽 노드,  크면 오른쪽 노드로 이동하는 식이다.

다만, 이진검색을 적용하려면 위의 사진과 같이 정렬된 형태를 유지해야 하며,

노드가 추가/삭제될 때,  정렬된 상태를 유지하도록 해야한다.

이진검색을 위한 균형유지

Unbalnced 상태에서는 이진검색의 성능이 떨어진다.

왼쪽의 Balanced 상태에서는 2번의 이동으로 6을 찾을 수 있지만,

오른쪽의 Unbalanced 상태에서는 5번을 이동해야만 6을 찾을 수 있다.

• Balanced        :  O(log n)
• Unbalanced  :  O(n)

즉, 데이터를 삽입/삭제할 때.

• Balanced 상태를 가능한 유지해야 하며, 
• 정렬된 상태를 유지해야 한다.

최대로 Balanced 된 일반적인 이진트리는 Complete 상태를 갖는다.

이진검색 트리

다음은 지금까지 설명했던 이론이 적용된 이진트리의 종류이다.

• AVL 트리

• B,  B+,  B* 트리

• R 트리

• Red-Black 트리

• ...

최대최소 트리

단순히 최대최소를 찾기위한 트리도 있으며,  이진검색 트리보다 약한 제약성을 가지고 있다.

데이터를 삽입/삭제해도 항상 루트노드가 Max/Min인 상태를 유지하는 트리이다.

• Max Heap 트리
• Min Heap 트리
• ...