Tree

Tree의 구조

• 노드와 브랜치로 이루어져 있는 사이클이 없는 데이터 구조
• 이진트리 형태의 구조로 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.

용어

• Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
• Child Node: 어떤 노드의 상위 레벨에 연결된 노드
• Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
• Sibling (Brother Node): 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

실제로 데이터를 넣을떄나 탐색할 떄 이진탐색트리의 적다 크다 조건을 가지고 빠르게 데이터를 찾고 넣을 수 있다.

이진 트리와 이진 탐색 트리

• 이진 트리: 노드의 최대 Branch가 2인 트리

• 이진 탐색 트리: 이진 트리에 다음과 같은 추가적인 조건이 있는 트리

  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음

이진 탐색 트리의 장점과 주요 용도

• 주요 용도: 데이터 검색(탐색)
• 장점: 탐색 속도를 개선할 수 있음

이진트리와 정렬된 배열간의 탐색 비교

이진 탐색 트리의 삭제

• 매우 복잡하기 때문에 경우를 나누어서 이해하는 것이 좋음

  Case1: 삭제할 Node가 Leaf Node인 경우

  Case2: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우

  Case3-1: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 왼쪽에 있을 때)

  Case3-2: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽에 있을 때)

• 삭제할 떄 노드가 두개인 경우 오른쪽자식중 가장 작은값 혹은 왼쪽자식 중 가장 큰값을 찾아서 올린다.이부분 외워두면 좋음
• 삭제하는부분은 알고리즘을 다 듣고 직접 작성해 보자

이진 탐색 트리의 시간 복잡도와 단점

시간 복잡도

• depth를 h라고 표기한다면, O(h)

• n개의 노드를 가진다면, h = log n에 가까우므로, 시간 복잡도는 O(log n)

  • 한번 실행시 마다 50%의 실행할 수도 있는 명령을 제거한다는 의미다. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미한다.

이진 탐색 트리의 단점

• 평균 시간복잡도는 O(log n)이지만, 이는 트리가 균형잡혀 있을 경우의 시간복잡도다.

• 다음과 같이 구성되어 있을 경우, 최악의 경우 링크드 리스트등과 동일한 성능을 보여준다. (O(n))