소개글

면접 대비겸 여러 블로그들을 참고하면서 정리해본 CS 지식들을 포스팅하고 있습니다.
만약 틀린 내용이 있다면 피드백은 언제나 환영합니다.
제 나름대로 요약한 내용이기 때문에 자세한 내용은 제일 아래쪽 참고 사이트에서 확인하면 좋을 것 같습니다!
말투는 편한 말투로 작성하니 양해 부탁드립니다.

Tree

특징

• 비선형 구조
• 계층적인 자료를 표현하는 데에 이용됨
  -사이클이 없는 그래프
• 간선, 루트 노드, 리프 노드, 인터널 노드 (루트포함)

트리 순회

Pre-Order (전위 순회)
부모 → 왼쪽 자식 → 오른쪽 자식

In-Order (중위 순회)
왼쪽 자식 → 부모 → 오른쪽 자식

Post-Order (후위 순회)
왼쪽 자식 → 오른쪽 자식 → 부모

Binary Tree (이진트리)

Perfect Binary Tree (포화 이진트리)

• 모든 레벨이 꽉 찬 이진트리

Complete Binary Tree (완전 이진트리)

• 위에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 채워진 이진트리

Full Binary Tree (정 이진트리)

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

Binary Search Tree (이진 탐색 트리)

• 왼쪽 자식 < 부모 < 오른쪽 자식을 만족하는 이진트리
• 중복되는 값이 있으면 안됨

Heap

• Complete Binay Tree 형태의 자료구조 - Array에 저장 가능
• 최대힙과 최소힙이 있음
• 부모 노드는 자식 노드보다 작거나 같음 (최소힙)
• 루트 노드에 최소 / 최대 값이 있기 때문에 해당 값은 O(1) 으로 찾을 수 있음
• 하지만 빼낸 뒤에 마지막 노드를 루트 노드로 옮긴 뒤 heapify 과정을 다시 거쳐야함 - O(log(n))

Red Black Tree

• Depth를 최소화하여 시간 복잡도를 줄이는 BST
• 조회, 삽입, 삭제에 O(log(n))이 걸림
• 삽입과 삭제를 할때마다 조건을 만족하도록 구조를 바꿔야함

조건

• 각 노드는 Red와 Black의 색깔을 가짐
• root와 leaf 노드는 Black (Nil 포함)
• Red 노드의 자식은 Black
• 모든 leaf 노드까지의 Black Depth는 같음 (경로에 있는 Black 노드의 개수)

참고 사이트

https://jud00.tistory.com/entry/자료구조-트리Tree란
https://yoongrammer.tistory.com/68
https://code-lab1.tistory.com/62