[자료구조] Tree

함민혁·2023년 8월 15일

tree 자료구조 트리

cs면접준비

목록 보기

25/43

Tree란?

비선형 자료구조. 계층적 관계를 표현하는 자료구조.
표현에 집중함.(무엇인가를 저장하고 꺼내야한다는 사고에서 벗어나야함)
값을 가진 노드와 노드들을 연결해주는 간선(Edge)로 이루어져있음

특징
정점이 N개인 트리는 반드시 N-1개의 간선을 가짐
루트에서 특정 정점으로 가는 경로는 유일함

이진 트리(Binary Tree)란?

각 정점이 최대 2개의 자식을 가지는 트리
루트 노드를 중심으로 두 개의 서브 트리로 나뉨. 재귀적인 정의여서 공집합도 이진 트리로 포함시킴

종류
완전 이진 트리 : 마지막 레벨을 제외하고 모든 정점이 채워져 있는 이진 트리
포화 이진 트리 : 마지막 레벨까지 모두 채워진 이진 트리
편향 트리 : 한 뱡향으로만 정점이 이어지는 트리

특징
정점이 N개인 이진트리는 최악의 경우 높이가 N이 될 수 있음
정짐이 N개인 포화 또는 완전 이진트리의 높이는 logN임
이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리에 응용됨

이진 탐색 트리(Binary Search Tree)란?

이진 탐색 트리에는 데이터를 저장하는 규칙이 있음. 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있음
이진 트리의 탐색연산은 O(logN)이지만 높이에 따라 O(h)의 시간 복잡도를 가짐. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문임.

규칙
이진 탐색트리의 노드에 저장된 키는 유일하다
부모의 키가 왼쪽 자식 노드의 키보다 크다
부모의 키가 오른쪽 자식 노드의 키보다 작다
왼쪽과 오른쪽 서브 트리도 이진 탐색 트리다

중위 순회(Inorder Traversal) : 트리의 노드를 "왼쪽 서브트리 - 현재 노드 - 오른쪽 서브트리" 순서로 순회하는 방법

Red-Black Tree

각 노드는 red, black이라는 색깔을 가짐
root node는 black, 각 leaf node는 black
특정 노드의 색이 red라면 두개의 children 모두 black인거임

그래프와 트리의 차이점이 무엇인가요?

둘 다 노드와 간선으로 구성된 자료 구조이지만, 사이클 여부, 루트 정의 여부, 간선이 단방향이냐 양방향이 가능하냐, 부모-자식 관계, 레벨과 깊이 개념이 적용되냐 안되냐 등등의 차이가 있습니다.
트리를 그래프의 특수한 형태로 볼 수 있음

이진트리와 이진탐색트리에 대해 설명해주세요.

이진트리는 각 정점이 최대 2개의 자식을 가지는 트리로, 루트 노드를 중심으로 두 개의 서브 트리로 나뉨.
이진탐색트리는 이진 탐색과 연결 리스트를 결합한 자료구조임. 이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 삽입,삭제가 가능하다는 장점이 있다. 이진 탐색 트리는 왼쪽 트리의 모든 값이 반드시 부모 노드보다 작고, 오른쪽은 모두 부모노드보다 크다는 특징이 있음. 탐색,삽입,삭제의 시간복잡도는 높이에 영향을 받아 O(h)다

이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?

트리의 노드를 "왼쪽 서브트리 - 현재 노드 - 오른쪽 서브트리" 순서로 순회하는 방법을 말하며, 중위 탐색을 하게 되면 정렬된 순서를 읽을 수 있다.

이진탐색트리의 한계점에 대해 설명해보세요.

트리 모양이 한쪽으로 치우친 편향 트리 구조가 되면 트리 탐색의 장점인 O(logN) 시간복잡도가 마치 배열마냥 O(N)에 가까워짐. 배열보다 많은 메모리를 사용해서 데이터를 저장했는데 탐색에 필요한 시간복잡도가 배열과 같아져버려서 비효율적이다. 그래서 이런 편향 트리가 되지 않게 해주는 rebalancing기법을 써서 BBST를 구현한다.

Red-Black-Tree에 대해 설명해주세요.

BST를 기반으로 하는 트리 형식의 자료구조이며, 탐색, 삽입, 삭제에 O(logN)의 시간복잡도가 소요됨.
동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어임
BST의 특성을 유지하며 삽입,삭제를 진행하며, Java Collection의 ArrayList 그리고 HashMap에서도 쓸정도로 효율이 좋고 중요한 자료구조임

Balanced Binary Search Tree와 그 종류에 대해 설명해주세요.