자료구조 : 트리(Tree)

트리(Tree) 구조

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

 

용어

• Node : 트리에서 데이터를 저장하는 기본요소
• Root Node : 트리 맨 위에 있는 노드
• Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
• Child Node : 어떤 노드의 상위 레벨에 연결된 노드
• Leaf Node : Child Node가 하나도 없는 노드
• Sibling (Brother Node) : 동일한 Parent Node를 가진 노드
• Depth : 트리에서 Node가 가질 수 있는 최대 Level

출처 : 위키백과

 

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

• 이진트리 : 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리(Binary Search Tree, BST) : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리 (왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음)

 

이진 탐색 트리의 장점

• 장점 : 탐색 속도를 개선할 수 있음
• 용도 : 데이터 검색

사이트 참고 https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node