트리 (Tree)

개념

: 'Node'와 'Branch'를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

용어

• 노드 (Node) : 정보의 단위로서, 트리에서 데이터를 저장하는 개체(기본요소)
• 가지 (Branch) : 노드와 노드를 연결하는 간선
• 부모노드 (Parent node) : 어떤 노드의 상위 노드
• 자식노드 (Child node) : 어떤 노드의 하위 노드
• 형제노드 (Sibling node, Brother node) : 동일한 부모노드를 가진 노드
• 루트노드 (Root node) : 트리의 최상단 노드
• 단말노드 (Leaf node, Terminal node) : 자식노드가 하나도 없는 트리의 최하단 노드
• 깊이 (Depth) : 트리에서 노드가 가질 수 있는 최대의 level(깊이)

특징

• 트리는 부모 노드와 자식 노드의 관계로 표현된다.
• 트리에서 일부를 떼어내도 트리 구조이다. (← 서브 트리)
• 파일시스템, 데이터베이스 시스템과 같이 계층적이고 정렬된 많은 양의 데이터를 관리하는 목적으로 사용된다.
• 큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 '탐색 기법'을 이용하여 빠르게 처리한다.

이진 트리 (Binary Tree)

개념

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

이진 탐색 트리 (Binary Search Tree)

개념

: 이진 탐색이 동작할 수 있도록 고안되어 효과적인 탐색이 가능한 자료구조로, 이진 트리에 조건이 붙은 트리

조건

: 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

동작원리

1. 루트 노드부터 방문한다.
2. 만약 타겟값이 루트 노드보다 크면 왼쪽 자식 노드는 확인할 필요가 없으므로, 오른쪽 자식 노드를 확인한다.
3. 만약 타겟값이 루트 노드보다 작으면 오른쪽 자식 노드는 확인할 필요가 없으므로, 왼쪽 자식 노드를 확인한다.
4. 타겟값과 현재 방문한 노드의 값이 일치할 때 까지 과정 2, 3번을 반복하다가 탐색을 마친다.

🔗 References

패스트캠퍼스 - 개발자 취업 합격 패스 with 코딩테스트, 기술면접