[자료 구조] 트리(Tree) - 1.구조 이해

* 해당 글은 패스트캠퍼스의 자료구조 알고리즘 강의를 듣고 정리하였습니다. 저작권은 패스트캠퍼스에 있습니다.

📌 트리(Tree)란

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

그 중에서 노드의 Branch가 최대 2개인 경우를 이진 트리라고 부른다.

 

✔️ 이진 트리 종류

• 이진 탐색 트리
• 완전 이진 트리 (Heap에서 사용)
• ...

 

✔️ 이진 트리에서 알아야 하는 용어

• 노드(Node) : 트리에서 데이터를 저장하는 기본 요소 (그림에선 동그라미임. data + branch 정보)
• 루트 노드(Root Node) : 트리 맨 위에 있는 노드
• 레벨 (Level) : 최상위 노드를 Lv0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄.
• 부모 노드 (Parent Node) : 어떤 노드의 상위 레벨에 연결된 노드
• 자식 노드 (Child Node) : 어떤 노드의 하위 레벨에 연결된 노드
• Leaf Node/ Terminal Node : Child Node가 없는 노드
• Sibling/ Brother Node : 자신과 동일한 Parent Node를 가진 노드
• 깊이 (Depth) : 트리에서 Node가 가질 수 있는 최대 레벨

이진 트리 용어

 

 

 

📌 이진 트리 vs 이진 탐색 트리(Binary Search Tree)

✔️ 이진 트리 : 노드의 최대 branch가 2개인 트리

 

✔️ 이진 탐색 트리 (Binary Search Tree : BST)

• 이진 트리에 추가적인 조건이 있는 트리
• 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다.

이진 탐색 트리

(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

 

 

 

 

📌  이진 탐색 트리 장점/ 용도

• 용도 : 데이터 검색(탐색)
• 탐색 속도를 개선할 수 있음.

이진 탐색 트리와 정렬된 배열 간의 탐색 비교

(출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)