Tree
Tree는 Array, LinkedList, Stack, Queue처럼 일직선 구조가 아니라 부모 자식 관계를 가지는 구조이다. 그래서 Tree는 계층이 있고 그룹이 있다.(계층과 그룹이 있는 이유는 각 노드가 하나 이상의 자식노드를 가지기 때문이다.) 더이상 자식이 없는 마지막 노드를 leaf라고 부른다.
Binary Tree(이진트리)
노드가 하나이상의 자식 노드를 가지면 트리라고 하는데 그 중에 자식노드가 최대 2개까지만 붙는 트리를 이진트리라고 한다. (최대 3개씩 붙는 트리는 Ternary Tree라고 한다.)
Binary Search Tree(이진 검색트리)
다른 조건 없이 노드의 자식노드가 최대 2개씩만 붙어있는 것이 Binary Tree이고 Binary Search Tree는 트리안의 데이터가 root노드 기준으로 왼쪽은 root노드보다 작은 값 오른쪽은 큰 값으로 정렬되어 있는 트리이다. 이진 검색트리는 모든 값들이 노드들을 기준으로 나누어져 있어서 값을 찾을 때 root노드를 기준으로 범위를 줄여가며 찾을 수 있다.
Complete Binary Tree(완전 이진트리)
완전 이진트리는 모든 노드들이 레벨별로 왼쪽부터 채워져 있는 것을 말한다. 트리를 만들면 노드들의 자식노드들이 생기는데 그 자식노드들이 만들어 질 때 왼쪽부터 채워지는 트리를 말한다.
Full Binary Tree
Full Binary Tree는 노드가 자식노드를 하나도 안가지거나 가진다면 2개를 가지는 트리이다.
Perfect Binary Tree
Perfect Binart Tree는 노드들이 각 레벨별로 구성될 수 있는 최대의 노드 수로 이루어진 트리를 말한다.(모든 노드들이 자식노드를 2개가지는 트리)
Perfect Binary Tree는 레벨의 수가 N일 때 노드의 개수가 2^N-1개이다.
Tree의 데이터를 가져오는 방법(Binary Tree Traversals)
Tree의 node들을 지정된 순서대로 방문하는 것
- Inorder(Left, Root, Right)
- Preorder(Root, Left, Right)
- Postorder(Left, Right, Root)
각 방법에 대해서 아래의 노드를 예시로 하여 데이터를 가져오는 방법을 알아보자
Inoeder(Left, Root, Right)
Root노드를 시작으로 먼저 왼쪽 leaf노드의 데이터를 가져오고 그 다름 leaf의 부모 노드의 데이터를 가져오고 그 다음 오른쪽 노드를 가져오는 방식으로 데이터를 가져온다. (5 -> 6 -> 13 -> 10 -> 11)
- 트리에 Root노드는 하나이다.
Preorder (Root, Left, Right)
Root노드의 데이터를 먼저 가져오고 그 다음 왼쪽, 오른쪽 순으로 데이터를 가져온다. (10 -> 6 -> 5 -> 13 -> 11)
Postorder(Left, Right, Root)
왼쪽, 오른쪽의 데이터를 먼저 가져오고 다 가져왔으면 Root노드의 데이터를 가져오는 방식 (5 -> 13 -> 6 -> 11 -> 10)
Binary Heaps
heap
heap은 최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기위해 고안된 완전 이진트리(Complete Binary Tree)를 기본으로 한 자료구조이다.
최소 Heap
작은 값이 항상 위에 노드에 있도록 만들어 트리의 root노드에 가장 작은 값이 오도록 하는 트리구조
최대 Heap
큰 값이 항상 위에 노드에 있도록 만들어 트리의 root노드에 가장 큰 값이 오도록 하는 트리구조
최소 힙에 노드 삽입하기
1.새로운 노드를 마지막 레벨에 완전 이진트리를 유지하며 생성한다.(왼쪽부터 노드생성)
2. 부모 노드와 비교를 해서 부모 노드보다 값이 작다면 값을 바꾼다.
3. 2번 과정을 반복한다. 더 이상 비교를 안한다면 새로 추가한 값이 root 노드에 도달하였거나 부모 노드가 새로 추가한 노드값보다 작은 것이다.
시간 복잡도: 최대 O(log n) (한번 비교할 때마다 노드의 수가 절반씩 줄기 때문에)
최소 힙에서 노드 꺼내오기
주로 최소값을 찾을 때 최소 힙을 이용한다. 최소 값을 꺼내오는 것은 root노드를 가져오면 된다. 그런데 root노드를 꺼내온 뒤 root노드에 값을 채워야 하는데 이때는 완전 이진트리의 마지막 레벨의 마지막 노드를 가져와서 root노드에 채운 후에 자식 노드(왼쪽, 오른쪽)들과 비교하여 가장 작은 노드가 위의 노드로 가도록 만들어 최소 힙을 만든다. 이 과정은 자식 노드들이 부모 노드보가 크거나 leaf노드에 도달했을 때 멈춤다.
시간복잡도: 최대 O(log n)
