[JAVA] 트리 개념 설명

트리 특징

• 비선형 자료구조 / 노드, 간선으로 이루어진다 / 하나의 루트 노트를 가진다
• 모든 노드는 하나의 서브트리(특정 노드와 하위 자손들로 이루어진 부분트리이다)
• 이진 탐색 트리(Binary Search Tree, BST)
  => 순서화된 이진 트리로 노드의 왼쪽 자식은 부모의 값보다 항상 작은 값을 가져야 하고 노드의 오른쪽 자식은 부모의 값보다 항상 큰 값을 가져야 한다(아래 추가적인 설명)
• 트리는 계층적인 구조를 가지고 있어 데이터를 계층적으로 표현할 수 있다 -> 현실 세계의 많은 문제를 효과적으로 모델링 가능하다
• 이진 탐색 트리의 경우 데이터를 정렬된 상태로 유지하므로 탐색, 삽입, 삭제 연산에 대해 평균적으로 O(log n)의 시간 복잡도를 가진다
• 자기 참조적인 구조 -> 효율적인 재귀 알고리즘 구현 가능
• 트리 순회 : 각 노드를 한 번씩 방문하는 과정(전위-루트,왼,오/ 중위-왼,루트,오/ 후위-왼,오,루트)
  출처 https://cdragon.tistory.com/19

단점

• 삽입 및 삭제의 복잡 : 트리의 구조를 유지하기 위해서
  => 특히, 불균형한 트리의 경우 트리의 재조정이 필요할 수 있어 추가적인 연산이 필요
• 메모리 사용 : 트리는 포인터로 연결된 노드 구조를 가지고 있기 때문에 메모리 사용이 비교적 크다
  => 트리의 균형을 유지하기 위해서는 메모리 사용이 더 증가한다
• 순회 순서의 의존성 : 트리의 구성으로 결정
  => 순차적으로 접근해야 하는 경우 순회 순서에 따라야 함으로 일반적인 순차 자료구조보다 복잡하다

이진 탐색 트리

• O(log2n)의 시간 복잡도
• 오름 차순으로 인덱스를 탐색 가능
• 삽입 : 루트와 비교 후 작다면 왼쪽으로 본인이 작으면 계속 왼쪽 내려감
• 삭제 : 까다로움(leaf노드라면 그냥 삭제, 자식이 한개라면 삭제 후 그 자리에 삽입)
  but 자식이 2개라면 아래 방식으로
  => 2가지 중 1개 선택(왼쪽 서브트리의 최댓값과 교체, 오른쪽 서브 트리의 최솟값과 교체)