신입 개발자 기술면접 질문 정리 - 자료구조
목차
- BST(Binary Search Tree)와 Binary Tree에 대해 설명하시오.
- RBT(Red-Black Tree)에 대해 설명하시오.
1. BST(Binary Search Tree)와 Binary Tree에 대해 설명하시오.
- 이진 탐색트리와 이진트리는 데이터 관리와 탐색을 효율적으로 하는 자료구조
이진 탐색 트리 (Binary Search Tree)
1) 정의
- 모든 노드가 자신의 왼쪽 서브 트리에는 자신 보다 작은 값을, 오른쪽 서브 트리에는 자신 보다 큰 값을 가지는 트리 구조
2) 검색, 삽입, 삭제
- BST 구조는 검색, 삽입, 삭제 작업을 평균 O(logN), 최악의 경우 O(N)의 시간 복잡도로 수행 할 수 있어 효율적인 데이터관리가 가능
이진 트리 (Binary Tree)
1) 정의
- 각 노드가 최대 두개의 자식 노드를 가지는 트리 구조.
- 이진 트리는 크게 정 이진 트리, 완전 이진 트리, 포화 이진트리등 여러 종류가 있다.
2) 특징
- BST와는 달리 노드간의 특별한 순서 관계가 업어도 되고, 더 자유로운 구조를 가지고 있다.
- 데이터의 삽입 삭제에 대한 구체적인 규칮ㄱ보다는 트리구조를 이용한 다양한 알고리즘을 구현하는데 초점이 맞춰저 있음
2. RBT(Red-Black Tree)에 대해 설명하시오.
- 이진 탐색 트리에 복잡도 문제를 해결하기 고안된 자료 구조
1) 정의
- 자기 균형 이진 탐색 트리로, 삽입, 삭제 및 검색 작업을 효율적으로 수행할 수 있도록 설계됨
2) 목적
- 이진 탐색 트리에서 발생 할 수 잇는 한쪽으로 치우침 현상을 줄여 검색시간(O(logN))의 일관성을 유지
3) 색상 규칙
- 모든 노드가 빨간색 또는 검은색으로 색칠되어 있으며, 특정 규칙을 만족시키는 구조를 가짐
4) 규칙
- 모든 노드는 ‘레드’혹은 ‘블랙’이다.
- 루트 노드는 ‘블랙’이다
- 모든 리프 노드(NIL)는 ‘블랙’이다.
- ‘레드’노드의 자식 노드는 모두 ‘블랙’이다. (‘레드’노드는 연속될 수없다.)
- 어떤 노드로부터 시작되는 모든 경로에는 같은 수의 ‘블랙’노드가 있다.
5) 장점 및 용도
5-1) 효율성
- 삽입, 삭제, 검색 연산을 최악의 경우에도 O(logN)의 시간 복잡도를 수행 할 수있다.
5-2) 균형유지
- 특정 규칙을 통해 트리의 균형을 유지하기 때문에 한쪽으로 치우침이 적어 탐색 시간이 일관되게 유지됨
5-3) 용도
- 맵, 셋 등의 자료구조 구현에 활용. 또한, 다양한 데이터베이스 시스템에 인덱스 구현에도 사용
출처
신입 개발자 기술면접 질문 정리 - 자료구조
댓글남기기