자료구조&알고리즘
[자료구조] 트리 Tree
파송송
2022. 8. 24. 14:46
728x90
트리
- Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
- 이진트리 (Binary Tree 형태, 가장 많이 쓰임)로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
용어
- Node : 트리에서 데이터를 저장하는 기본 요소 (Branch 정보 포함)
- Root Node : 트래 맨 위에 있는 노드
- Level : 최상위 노드를 Level 0으로 하여, 하위 Branch로 연결된 노드의 깊이
- Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
- Child Node : 어떤 노드의 상위 레벨에 연결된 노트
- Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드
- Sibling (Brother Node) : 동일안 Parant Node를 가진 노드
- Depth : 트리에서 Node가 가질 수 있는 최대 Level
- 이진트리 : 노드의 최대 Branch가 2인 트리
- 이진탐색트리 BST Binary Search Tree : 이진 트리에 조건이 붙은 트리
- 조건 : 왼쪽 노드는 해당 노드보다 작은 값을 가지고 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음
- 데이터 검색(탐색)에 자주 쓰임
이진트리탐색과 배열의 탐색 비교
728x90