Binary Search Tree - BST
1. Binary Search Tree
BST가 무엇인가?
모든 노드의 left sub tree들은 해당 노드의 값보다 작은 값들만 가지고,
모든 노드의 right sub tree들은 해당 노드의 값보다 큰 값들만 가진다.
그렇다면 예시를 한 번 살펴보자.
1)은 12와 10이 맞지 않기에 BST라고 할 수 없다.
2)는 BST가 맞다.
3)은 헷갈릴 수도 있지만, 55를 살펴보면 60보다 작기에, 55를 add할 때, 60의 left sub tree로 들어가야 한다. 따라서 BST라고 할 수 없다.
2. Maximum Minimum
Binary Search Tree의 minimum
Tree의 가장 왼쪽에 존재 : root node를 기준으로 계속 왼쪽을 따라가면 나오는 값
Binary Search Tree의 minimum
Tree의 가장 오른쪽에 존재 : root node를 기준으로 계속 오른쪽을 따라가면 나오는 값
3. 순회 - inorder traversal / preorder traversal / postorder traversal
중위 순회 : Inorder traversal
Root node를 기준으로 재귀적으로 left sub tree 순회
현재 노드 방문 (e.g. 값 출력)
재귀적으로 right sub tree 순회
즉, 더 이상 왼쪽 노드가 없으면 출력!
전위 순회 : Preorder traversal
Root node를 기준으로 현재 노드 방문 (e.g. 값 출력)
재귀적으로 left sub tree 순회
재귀적으로 right sub tree 순회
왼쪽으로 따라 가는데 방문한 노드 바로 출력!
후위 순회 : Postorder traversal - 더 이상 갈 노드가 없으면 출력!
Root node를 기준으로 재귀적으로 left sub tree 순회
재귀적으로 right sub tree 순회
현재 노드 방문 (e.g. 값 출력)
4. Node’s successor / predecessor
Node의 successor(후임자) 가 무엇인가?
해당 노드 보다 값이 큰 노드들 중에서
값이 가장 작은 노드
Ex) 20의 successor = 30 17의 successor = 20
10의 successor = 15
Node의 predecessor(선임자) 가 무엇인가?
해당 노드 보다 값이 작은 노드들 중에서
값이 가장 큰 노드
Ex) 20의 successor = 17 17의 successor = 15
10의 successor = 5
5. Binary Search Tree methods - 삭제/검색
Insert : 삽입
Insert를 활용한 Binary Search Tree 생성
Insert(50)
Insert(70)
Insert(90)
Insert(99)
Insert(80)
Insert(30)
Insert(40)
Insert(20)
Delete : 삭제
앞의 생성한 Binary Search Tree에서 node 검색 후 delete
delete(20) -> null
delete(30) -> 링크를 변경
delete(50)
-> 자녀가 둘 인 경우, right sub tree에서 제일 값이
작은 노드가 삭제될 노드를 대체
add(85)
delete(70)
Delete : 삭제
앞의 생성한 Binary Search Tree에서 node 검색 후 delete
delete(20) -> null
delete(30) -> 링크를 변경
delete(50)
-> 자녀가 둘 인 경우, right sub tree에서 제일 값이
작은 노드가 삭제될 노드를 대체
add(85)
delete(70)
6. 시간 복잡도 / 장단점
- 시간 복잡도
- 장단점
장점
1) 삽입 삭제가 유연
2) 값의 크기에 따라 left right sub tree들이 구성되기에 avg O(logN)으로 보통은 빠르다
단점
1) 트리가 한 쪽으로 편향되어 있다면, 수행시간 악화
=> 스스로 균형 잡는 AVL tree, Red-Black tree
