알고리즘 기초 정리 1 (트리, 노드, 이진트리, 링크표현법, 이진탐색트리)

1. 리스트, 스택, 큐는 선형구조이며, 트리는 계층적인 구조의 비선형 자료구조이다.

2. 트리는 부모와 자식관계의 노드(트리의구성요소)들로 만들어 진다. 루트는 부모가 없는 노드이다.

3. 트리에서 레벨은 각층의 번호이며, 높이는 최대 레벨이다. 차수는 자식 노드의 개수이며, 트리의 차수는 노드의 최대 차수이다.

4. 트리는 이진트리와 비이진트리가 존재한다. 이진트리는 모든노드가 2개의 서브트리를 가지고 있는 트리이다. (최대2개)

5. 노드의 개수가 n개이면 간선의 개수는 n-1 이다. (루트노드를 제외하고 모두 부모노드를 가지기때문이다.)

6. 이진트리에서 최소노드의 개수는 높이이며, 최대는 2^h -1 개의 노드이다.

7. 링크표현법: 포인터를 활용하여 부모노드가 자식노드를 가르키는 표현법이다. 노드는 구조체, 링크는 포인터로 표현한다.

8. 순회는 노드들의 체계적으로 방문하는것이며,그 예로 전위순회, 중위순회, 후위순회가 있다. 스택을 사용한다.

9. 레벨 순회는 레벨순으로 검사하는 순회방법이다. 레벨 순회는 큐를 사용한다.

10. 이진 탐색 트리는 탐색작업을 효율적으로 하기위한 자료구조로서, 이진 탐색트리르 중위 순회하면 오름차순으로 정렬된 값을 얻는다.

11. 이진탐색트리에서 탐색, 삽입, 삭제 연산의 시간복잡도는 트리의 높이에 비례한다. 한쪽으로 치우쳐진 이진트리의 경우 순차탐색과 시간복잡도가 같다.