'트리' 에는 알고 있어야 할 기본적인 용어들이 있다.
트리
node 와 branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조. 트리 중 이진트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨.
- node : 트리에서 데이터를 저장하는 기본요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
- root : 트리 맨 위에 있는 노드
- level : 최상위 노드를 level0 로 하였을때, 하위 branch로 연결된 노드의 깊이를 나타냄
- parent node : 어떤 노드의 다음 레벨에 연결된 노드
- child node : 어떤 노드의 상위 레벨에 연결된 노드
- leaf node : child node가 하나도 없는 노드
- sibiling(brother node) : 동일한 parent node를 가진 노드
- depth : 트리에서 node 가 가질 수 있는 최대 level
이진트리와 이진탐색 트리
이진트리와 이진탐색트리는 다르다.
- 이진트리: 노드의 최대 branch가 2인 트리
- 이진탐색트리(BST): 이진트리에 다음과 같은 추가적인 조건이 들어간다
- 왼쪽 노드는 해당 노드보다 작은값!!, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음.(조건이 있고, 기준이 생김)
someone's opinion of you does not have to become your reality