728x90
반응형
Binary Search Tree
Youtube - DSU SW Community
Binary Search Tree
- left subtree of x have keys < x
- right subtree of x have keys > x
- Binary Search Tree는 여러 가지 다양한 방법으로 구현이 가능하다.
Searching in a tree
- tree *l = 트리의 root 노드를 가리킨다.
- item_type x = x 값 찾기
→ l을 root 노드로 가지는 트리에서 x 값을 가지는 노드 찾기
- l이 NULL이면 NULL을 반환, x를 찾으면 해당 노드를 반환한다 (l)
- Binary search tree 특성상 조건문으로 x를 찾을 때 까지 검사하고, 재귀적으로 tree를 호출한다.
Finding minumum / maximum element in a tree
- 최소값을 찾으려면 Binary search tree 특성상 계속 왼쪽으로 값을 비교해 가면서 최솟값을 찾아야 한다.
- 최댓값의 경우에는 계속 오른쪽으로 값을 비교해 가면서 최댓값을 찾아야 한다.
Traversing in a tree
- 내가 이해하기로는 깊이 탐색으로 이해했다.
- 왼쪽으로 NULL이 나올 때 까지 계속 탐색하고, 오른쪽으로 NULL이 될 때까지 탐색하는 방법이다.
Insertion in a tree
- Binary search tree 에 값을 삽입하려고 하는 내용이다.
- NULL이 있는 곳까지 찾는 방법은 travesing in a tree와 같은 형식이다.
- NULL을 찾았을 때 동적할당을 통해 노드를 삽입한다.
- 임시 포인터변수 *p를 통해 넣고자 하는 값 x를 넣는다.
- p의 left와 right는 NULL로 만들어 주고 p의 parent를 삽입하려는 parent를 가리키고 있다.
Deletion from a tree
가. 지우려는 노드의 자식이 없을 경우 : 그냥 지우면 된다.
나. 지우려는 노드의 자식이 1개일 경우 : 노드를 지우고 그 자리를 자식으로 대체한다.
다. 지우려는 노드의 자식이 2개일 경우
- 2가지 방법이 있다.
- ① 왼쪽에서 최댓값을 사용 ② 오른쪽에서 최솟값을 사용 둘 중 아무거나 써도 상관없다.
- 위 그림은 ② 번 방법을 사용하고 있다.
- E의 값을 복사해서 D에 넣고 원래 E를 삭제한다.
- E의 자식의 수에 따라 가, 나, 다의 경우를 반복한다.
How good are binary search trees?
- 최악의 경우 binary search trees는 a skinny linear height tree가 될 수 있다.
ex )
Rotation
- 최악의 경우를 해결하기 위해 쓰이는 몇 가지 방법 중 하나다.
- rotate left를 기준으로 말하면, β는 초록 노드를 children으로 가지고있는 parent 노드 쪽 보다 더 큰 값을 가진다.
→ (Binary search tree의 특성상)
- 그래서, rotate left를 하고난 뒤, β는 노란 노드 children 중 최댓값을 가지도록 노드를 붙여준다.
728x90
'프로그래밍 > 자료구조' 카테고리의 다른 글
| [자료구조] - Heap (0) | 2022.02.18 |
|---|
