ch8_BST(Binary Search Tree)

‍신정아[학생](소프트웨어융합대학 컴퓨터공학과)·2022년 1월 9일

자료구조

목록 보기

2/6

BST(Binary Search Tree)는 트리의 특수한 경우임

해당 챕터의 예제 연산들은 array-based가 아니라 직접 포인터(right,left)를 이용해서 구현되어 있음

Basic Terms

Root Node는 각 트리 당 유일함
Leaf Node: 자식 노드가 없는 노드(마지막 레벨이 아니더라도 가능함. 자식만 없으면 됨)
Level: 루트를 기준으로! 루트와 몇 단계 차이나는지(루트에서 몇 개의 가지를 거쳐야 하는지)

Subtree: 부분 트리. 전체 중 일부만! 있는 트리
Ancestor of a node: 루트에서 해당 노드까지의 경로에 있는 모든 노드들(자기 자신 제외)

Descendant of a node: 어떤 한 노드로부터 leaf 노드까지 가는 경로에 있는 모든 노드들(자기 자신 제외)

Level (Depth) of a node: 루트를 기준으로! 루트와 몇 단계 차이나는지(루트에서 몇 개의 가지를 거쳐야 하는지)
즉 Level == Depth
Height of tree: number of levels(레벨의 수)- 그런데 level은 0부터 시작하므로 level2면 height는 3이 됨(즉 height=max(level)+1)
Complete Binary Tree: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다(왼쪽부터 채워진다).
Full Binary Tree: 모든 잎이 동일한 수준에 있고 모든 잎이 아닌 노드에 두 개의 자식을 갖는 이진 트리
Full Binary Tree는 Complete Binary Tree가 될 수 있지만, Complete Binary Tree는 Full Binary Tree가 될 수 없다.

What is a Binary Tree?(아직 Binary Search Tree아님)

각각의 노드는 최대 2개의 자식 노드를 가질 수 있다
- 선행하는 코드는(predecessor node) 부모라고 불린다
- 노드의 시작은 root임(no parent, 즉 부모가 없는 노드는 root node)
- 자식이 없는 노드는 leaf node임
Depth가 가장 깊은 것이 leaf node? No!!!!!!!!!!!!!!!
Depth가 가장 깊진 않아도 자식만 없으면 leaf node이다.
각 노드는 루트로부터 유일한(unique)경로(path)를 가진다.
- 왜냐면 순환 관계(cycle)가 없기 때문임
- 사실 이거는 binary tree라기보다는 그냥 tree자체의 특성임
- 트리라서 순환이 존재하지 않음! 오직 상하 관계만 있음(평등 관계 없음)
- 각 노드에 대해서 부모 노드는 단 하나만 존재한다.

number of nodes N of a full tree(binary tree에서 자식 노드가 가득 참.) with height h?

The max #nodes at level l is 2^l

$N=2^0+2^1+....+2^{h-1}=2^h-1$ (reminder: height=max(level)+1, level은 0부터 시작하므로)

위의 식을 변형하면 전체 개수로부터 h를 구할 수 있다

$h=log(N+1)$

📌 즉, 높이(height)로 전체 노드의 수를 구할 수 있고, 전체 노드의 수로부터 높이 정보를 얻을 수 있다.

(그냥) Binary Tree: 각 레벨별로 하나씩 순차적으로 찾는다 - 최악의 경우 O(N) → 즉 linked list보다 더 나을 게 없음 그래서 Binary Search Tree가 나왔다!

이제부터 본격적인 Binary Search Tree에 대한 내용(이전까지는 그냥 Binary Tree)

Binary Search Tree

Binary Tree에서의 아주 특수한 형태임
1. 각각의 노드는 구분되는 data value를 가진다
2. key value들은 “크다”,”작다”의 기준으로 비교된다
3. 트리에 있는 각 노드의 키 값은 오른쪽 하위 트리의 모든 키 값보다 작고 왼쪽 하위 트리의 모든 키 값보다 크다. (즉 부모보다 작으면 왼쪽 서브트리에 추가, 부모보다 크면 오른쪽 서브 트리에 추가)
SHAPE 📌 BST(Binary Search Tree)의 SHAPE은 **각 노드들의 key value들과 그들의 삽입 순서에 달려있다.** →따라서 최악의 경우 그냥 일렬로만 추가되어 (계속 큰 값들만 추가되면) 일반적인 Linked List와 다를 게 없을 수도 있게 됨 📌 Is BST better than searching a linked list? YES!!!!!!!!!—>O(logN) ; 최악x, 평균적인 경우 📌 **Does the order of inserting elements into a tree matters?** →Yes. 어떤 경우에는 아주 unbalanced tree를 만들어낸다 →Unbalanced tree are not desirable because SEARCH TIME IS INCREASED 📌 **재귀는 파라미터가 포인터변수라도 레퍼런스로 처리해야함(레퍼런스로 전달해야**) →왜냐면 어쨌든 포인터 변수도 변수이기 때문에, pass by value로 전달됨. (즉, 자식 노드에서 지역변수가 됨), call by value로 포인터 변수를 받으면 함수내에서 실컷 실행하고 리턴되어 다시 부모 노드로 거슬러 올라갈 때, 했던 내용들이 모두 없어짐(지역 변수의 특성) —>**메모리 누수가 생김**(할당된 메모리 공간은 있는데 가르키는 포인터가 없어지게 됨) +) ch7_RECURSION 참조 +) dangling pointer ←—→ memory leak - **dangling pointer**는 가르키는 포인터는 있는데 해당되는 메모리 공간이 없어진 것이고(해제 등에 의해) - **memory leak**은 할당된 메모리 공간은 있으나 그걸 가르키는 포인터가 없는 것임(없어진 것임-할당된 메모리를 못 쓰는 거임.) - 서로 반대개념. 제대로 이해하자 --- ## DELETE ITEM IN BST 노드를 삭제할 때는 다음 세 가지의 경우 중 하나임을 반드시 고려해야 한다! (해당되는 경우를 찾아 적절하게 대응해야 한다.) 1. **DELETING A LEAF(리프 노드를 삭제)** →제일 단순함. 그냥 리프 노드의 연결만 끊으면(삭제하면) 됨 2. **DELETING A NODE WITH ONLY ONE CHILD(자식이 하나만 있는 노드 삭제)** →그 하나뿐인 자식을 (삭제될) 부모 자리로 끌어올림 3. **DELETING A NODE WITH TWO CHILD(자식이 두 명인 노드 삭제)** → 좌측 subtree의가장 오른쪽 leaf node를 (삭제될) 부모 노드로 땡겨옴 → 혹은 우측 subtree의 가장 왼쪽 leaf node를 (삭제될) 부모 노드로 땡겨옴

Tree Traversal

Tree Traversal은 트리의 모든 노드들을 방문한다는 것을 의미함
“visit(방문)”이라는 것은 해당 노드의 값으로 어떤 행동을 한다는 것 (ex) 출력
세 가지 타입이 있음
- InOrder Traversal : 자신이 중간
  - 결론적으로 크기 순으로 방문하는 것이 됨
  - left→자기 자신→right
- PostOrder Traversal : 자신이 제일 마지막
  - left→right→자기 자신
  - 즉 리프들을(자식들을) 먼저 접근하는 셈이 되므로, 삭제시에 유용함.
  - 삭제할 때 루트부터 지우면.........눈물.....
- PreOrder Traversal : 자신이 제일 처음
  - 자기 자신→left→right
  - 수학 공식등을 표현하고 싶을 때 연산자와 항의 관계에 적절함