📝Tree란?

방향성이 있는 비순환 그래프로 임의의 노드에서 다른 노드로의 경로가 유일해 싸이클이 없고, 모든 노드가 연결되어있는 자료구조이다.

이진트리

자식 노드가 최대 두개인 노드들로 구성되어 있는 트리로 다양한 종류의 트리들이 있다.

1. 포화이진트리(PBT)

• 모든 레벨의 노드가 채워져있는 상태의 트리

2. 정이진트리(FBT)

• 모든 노드가 0 또는 2개의 자식 노드를 가지는 트리

3. 완전이진트리(CBT)

• 노드를 삽입할 때, 왼쪽에서 차례대로 삽입하는 트리

4. Heap

• 쌓아 올린다는 뜻에 맞게 부모보다 자식이 항상 큰 값, 혹은 작은 값을 가지는 트리(우선순위 큐, 힙 정렬 등에 쓰임)

5. 이진탐색트리(BST)

• 검색, 삽입, 삭제에 효율적인 정렬 개념이 반영된 이진트리 구조이며 node의 한쪽의 sub tree는 항상 작은값을가지고 반대는 항상 큰 값을 가지는 이진탐색트리이다.

이진 탐색트리의 조회,삽입,삭제 시간복잡도는 O(logn이며) 최악의 경우는 O(n)이 된다. 이러한 최악의 경우를 피하기 위해 AVL과 Red-Black Tree 자료구조가 고안되었다.

AVL트리는 일명 자가균형이진탐색트리로써 이름 그대로 스스로 균형을 잡는 데이터 구조이다. 왼쪽과 오른쪽 서브트리 레벨의 차이가 1보다 커지면 데이터를 회전시켜 노드 간 균형을 잡아준다.

Red-Black트리 또한 이진탐색트리의 균형을 잡아주는 역할을 하는 트리이며 설명이 길기 때문에 다음 참고 사이트의 링크를 올려보기로 한다.
https://blogshine.tistory.com/m/102 참고

💡결론

- 트리: 저장된 데이터를 더 효과적으로 탐색하기 위해서 사용하는 방향성을 가진 데이터 자료구조