트리 구조

트리 데이터 구조는 데이터를 계층으로 정렬한다.

• 노드:데이터를 저장하며, 키(데이터식별)와 값(저장된데이터)을 포함할 수 있음.
• 루트노드: 트리구조의 맨 위 노드
• 부모노드: 상위노드
• 자식노드: 하위노드
• 리프노드:말단노드, 더이상 자식노드를 갖지않는 마지막 노드
• 에지:트리를 연결하는 선
• 서브트리:하위트리,노드하나와 자식노드로 구성된 트리

1. 이진트리

가장 많이 사용되는 데이터 구조. 각 부모 노드가 항상 2개의 자식 노드와 연결

이진탐색트리 : 모든 노드의 키는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다.

1의 위치: 가장 작은 키, 14위치: 가장 큰 키

2. AVL트리

하나의 자식 노드를 갖는 불균형 이진트리의 균형을 조정하여 최소높이로 만든것.

높이 차이를 감지하면 트리회전으로 조정한다. 시간 복잡도는 O(logn)이다.

왼쪽이 불균형상태.

+RB트리(모든 노드가 빨강(R) 또는 검정(B)): AVL트리와 비슷하지만, 트리회전수가 적어서 더 효율적임.

3. B트리

데이터베이스 시스템을 설계할 때 사용하는 데이터 구조. 자체적인 균형 조정 기능

자식노드 3개이상을 갖는 부모노드가 있음.

B트리 구조

4. 힙(heap)

이진트리 데이터 구조이며, 값이 최대 혹은 최소인 노드에 빠르게 접근해야하는 응용프로그램에서 적합

 - 최대힙:루트노드가 가장 큰 값이고 노드의 각각의 값이 부모노드보다 작거나 같도록 구성

 - 최소힙:루트노드가 가장 작은 값이고 노드의 각각의 값이 부모노드보다 크거나 같도록 구성