[자료구조] #7_1 트리

트리 구현시 로직이 많이 들어가서 알고리즘 같은 느낌을 준다.

 

구현하기 복잡하기 때문에 자료구조 중에서 면접에서 자주 질문이 나오는 편이다.

---

 

** 트리(Tree) 구조

• Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 실사용 예: 이진 트리의 형태로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

 

 

** 용어 정리

• Node: 트리에서 데이터를 저장하는 기본 요소. (데이터 + 연결 노드의 Branch 정보)
• 루트 노드: 트리 맨 위에 있는 노드
• 레벨: 어떤 노드가 위치한 트리의 층
• Parent Node: 어떤 노드의 상위 레벨에 있는 노드
• Child Node: 어떤 노드의 하위 레벨에 있는 노드
• Leaf Node: Child 노드를 가지지 않는 노드
• Sibling (Brother Node): 동일한 Parent 노드를 가지는 노드
• Depth: 트리에서 노드가 가질 수 있는 최대 레벨(높이)

 

 

 

** 이진 트리와 이진 탐색 트리

• 이진 트리: 노드의 최대 브랜치가 2인 트리
• 이진 탐색 트리(Binary Search Tree, BST): 이진 트리에서 다음과 같은 추가적인 조건을 만족하는 트리
  • 왼쪽 노드는 탐색하려는 노드보다 작은 값을 가지고 있어야 한다.
  • 오른쪽 노드는 탐색하려는 노드보다 큰 값을 가지고 있어야 한다.

 

클릭시 출처로 이동

 

 

 

** 이진 탐색 트리

• 주요 용도: 데이터 검색.
• 장점: 탐색 속도를 개선할 수 있음.
• 단점: 
• 탐색 시, 배열과 비교

 

클릭시 출처로 이동