•
정의
◦
비선형 자료구조로 노드로 구성된 계층적 자료구조이다.
◦
그래프의 일종으로 Cycle을 이루지 않는 그래프로 Node와 Edge가 존재한다.
▪
Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 정보 포함)
▪
Root Node: 최상위 노드
▪
Level: 최상위 노드의 Level을 0이라 하였을 때, 최상위 노드로부터 경로의 길이값
▪
Parent Node: 어떤 노드의 하위 레벨에 연결된 노드
▪
Child Node: 어떤 노드의 상위 레벨에 연결된 노드
▪
Leaf Node: Child Node가 하나도 없는 노드
▪
Sibling: 동일한 Parent Node를 가진 노드
▪
Depth: 트리에세 Node가 가질 수 있는 최대 Level
•
특징
◦
트리에 또 다른 트리가 존재하는 재귀적 자료구조이다.
◦
데이터를 순차적으로 저장하지 않는 비선형 자료구조이다.
◦
Binary Tree, Binary Search Tree, B-Tree, Heap Tree 등 다양한 종류가 존재한다.
▪
Binary Tree: Node의 브랜치의 갯수가 최대 2개인 트리
▪
Binary Search Tree: 이진 트리에 제약조건을 추가한 트리, 왼쪽 노드는 부모 노드보다 작은 값, 오른쪽 노드는 부모 노드보다 큰값을 저장하는 제약 조건이 존재한다.
◦
주로 데이터 검색에 사용되며 탐색 속도가 빠름
◦
◦
•
용도
◦
주로 이진 트리 형태는 탐색 알고리즘 구현을 위해 많이 사용된다.
▪
배열에서 특정 값을 찾고자 할 때 최악의 경우 O(N)이나 이진 탐색 트리의 경우 최악의 경우 O(log N)기 때문이다.
•
Binary Search Tree란?
◦
이진탐색트리는 정렬된 Tree, 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 right subtree에는 그 node 값보다 큰 값들을 지닌 node들로만 이루어져 있는 binary tree, 검색과 저장, 삭제의 시간복잡도는 모두 O(log n)이고 worst case는 한 쪽으로 치우친 tree가 됐을 때, O(n)
•
Hash Table이란?
◦
효율적인 탐색을 위한 자료구조로써 key-value 쌍으로 데이터를 입력받는 자료구조, hash function h에 key값을 입력으로 넣어 얻은 해시값 key를 위치로 하여 key-value 데이터 쌍을 저장, 저장, 삭제, 검색 모두 O(1)
•
데이터 삽입, 조회, 삭제
•
삽입
◦
현재 노드를 루트 노드부터 시작하여 삽입할 값과 현재 노드의 값을 비교해 이동하다 삽입될 공간의 브랜치가 비어있으면 삽입
•
조회
◦
주어진 키 값이 루트 노드의 키 값과 같으면 탐색에 성공
◦
주어진 키 값이 루트 노드의 키 값보다 작으면 왼쪽 서브트리를 탐색
◦
주어진 키 값이 루트 노드의 키 값보다 크면 오른쪽 서브트리를 탐색
•
삭제
1.
Leaf 노드인 경우
: 부모 노드의 연결을 삭제
2.
하나의 서브트리만 가지고 있는 경우
: 해당 노드를 삭제한 후, 서브 트리를 삭제된 위치에 붙여준다.
3.
두개의 서브트리를 가지고 있는 경우
: 현재 노드의 좌측 서브트리에서 가장 큰 값과 우측 서브트리의 가장 작은 값 중 한 값으로 현재 노드를 대체한다.
5. 이진 탐색 트리의 시간 복잡도와 단점
1.
시간 복잡도
•
depth를 h라고 표기한다면 O(h)
•
n개의 노드를 가진다면 h = log n에 가까우므로 시간 복잡도를 log n이라고 하는 것
2.
이진 탐색 트리 단점
•
데이터의 구성이 불균형할 때, 최악의 경우 링크드 리스트와 동일한 성능을 보여줌, 이를 방지하기 위해 B-트리 등이 존재
