Tree

Tree

Tree(트리)

데이터들을 나무를 뒤집은 형태로 저장한다.
부모와 자식 노드들로 이루어진다.
차수 : 어떠한 노드가 가지고 있는 자식 노드들의 개수
이진 트리 : 차수가 2인 트리

ex) 인덱스 트리 : 자식 노드들의 구간 합이 부모 노드에 저장된 값
정렬 상태를 유지할 수 있다.
Heap 구조의 트리이다. (저장된 값 중 최소/최대 값을 리턴하고, 나머지를 정렬하여 저장한다.)
시간복잡도 : 트리의 높이만큼 걸린다. O(Log(N))

KEY WORD : 이진 트리, 노드, 부모 노드, 자식 노드, O(Log(N))

---