TIL2: 자료구조_TREE

자료구조_TREE

📌 TREE 구조를 보기에 앞서.. 자료구조 사용 이유?

자료구조(Data Structure)

자료구조를 굳이 왜 만들어놓았는가!에 대한 근본적인 질문이 떠올라서 찾아본 “자료구조를 사용하는 이유?”

자료구조를 배우는 이유는 데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해서이다.

많은 자료구조를 알아두면, 상황별 적합한 타입의 자료구조를 사용해 데이터를 빠르게 정리하고 활용하여 문제를 해결할 수 있다.

데이터를 체계적으로 정리하여 저장해두는 것이 데이터를 활용하는데 훨씬 유리하다.

TREE

1. 개념

• 트리구조란? 노드로 이루어진 구조
• 트리구조는 무방향의 그래프로 계층적인 자료이다.
• 트리구조는 데이터를 순차적으로 나열시킨 선형구조가 아니라, 여러개의 데이터가 존재할 수 있는 비선형 구조이다.
• 트리구조는 계층적이고 위에서 아래로만 뻗어나가 사이클이 없다.

  1-1) 용어정리

  ◼ 노드: 트리를 구성하는 각각의 요소(데이터)
  ◼ 간선(edge): 노드를 연결하는 선
  ◼ 루트: 트리구조의 시작점
  ◼ 부모노드
  ◼ 자식노드
  ◼ 리프: 자식노드가 없는 노드
  ◼ 깊이(depth): 루트로부터 하위계층의 특정 노드까지의 깊이
  

• 루트 노드의 깊이는 0이다.
  ◼ 레벨(level): 트리구조에서 같은 깊이를 가지고 있는 노드를 묶어서 같은 레벨로 표현할 수 있고, 그런 노드들을 형제노드라고 한다.
  ◼ 높이(height): 리프노드를 기준으로 루트까지의 높이
  
• 부모노드는 자식노드의 가장 높은 height값에 +1한 높이를 가진다.
  ◼ 서브트리: root에서 뻗어나온 큰 트리 내부에 트리 구조를 가지 작은 트리
  

1-2) 실사용 예제 => 컴퓨터 디렉토리 구조

2. 이진트리(Binary Tree) & 이진탐색트리(Binary Search Tree)

트리구조는 특징에 따라 여러 이름으로 불리는데, 그 중 많이 사용되는 트리가 이진트리와 이진탐색트리이다.

☝ 이진트리(Binary Tree)

• 자식노드가 최대 두 개인 노드들로 구성된 트리
• 자식노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 바꿀 수 있다.

1) 정이진트리: 각 노드가 0개 혹은 2개의 자식 노드를 가진다.
2) 완전이진트리: 마지막 레벨을 제외한 모든 노드가 가득 차있어야 하고, 마지막 레델의 노드는 왼쪽 노드가 채워져야 한다.
3) 포화 이진 트리: 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워있는 트리이다.

☝ 이진탐색트리(Binary Search Tree)

• 이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징
• 균형잡힌 트리가 아닐 때, 한쪽으로 몰릴 수 있어 이때에는 시간이 더 걸리기 때문에 해결해야한다.
• 균형이 잡히지 않는 트리 탐색 문제는’트리구조를 재조정’함으로써 해결할 수 있다.

간단한 이해를 원하시면👉 https://bit.ly/3mDz09M
조금 더 딥하게 이해하고 싶으면👉 https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html