본문 바로가기

# Foundation/자료구조

이진트리 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 트리
  • ...


'# Foundation > 자료구조' 카테고리의 다른 글

우선순위 큐 ADT  (0) 2019.02.09
힙 ADT  (0) 2019.02.08
트리 ADT  (0) 2019.02.06
그래프 ADT  (0) 2019.02.06
덱 (데크)  (0) 2019.02.04