# Binary Tree & Binary Search Tree
- Tree 는 Google Interview 에서 가장 많은 비중을 차지하는 주제로, Tree 와 Binary Search Tree 를 활용한 문제들은 기본적으로 나올 것 같다.

Binary Tree
---
- Binary Tree는 left child 하나, right child 하나, **최대 2개의 child**를 가질 수 있는 Tree를 의미한다.
- Binary Tree 에도 종류가 여러가지가 있는데 `perfect binary tree`, `complete binary tree`, `full binary tree`가 있다.
- Perfect binary tree 는 **leaf 노드의 레벨이 모두 같은 binary tree**이고, 모양을 봤을 때는 빈 노드가 없이 꽉 찬 tree 라고 해서 perfect binary tree 라고 부른다.
- Complete binary tree 는 perfect binary tree 보다 더 상위 개념으로, leaf 가 모두 동일하진 않지만, **가장 높은 레벨에 있는 leaf 노드의 level과 가장 낮은 레벨에 있는 leaf 노드의 height 의 최대 차이는 1 밖에 되지 않는다**. Complete binary tree 는 **왼쪽에서 오른쪽으로 노드를 채워나가는 방식**이기 때문에 level의 차이가 최대 1만 닌다.
- Full binary tree 는 **자식 노드의 개수가 0개 이거나 2개**인 것을 보고 full binary tree 라고 부른다.
- Complete binary tree 의 대표적인 예로 `heap` 이 있다. heap 은 우선순위 큐를 구현하는데 사용하는 가장 대표적인 자료구조이다. Complete binary tree 는 부모와 자식 노드에 바로 접근이 가능하기 떄문에 Array로 구현할 수 있다. 현재 노드의 위치를 $idx$라고 할 때, 부모의 위치는 $ceiling(idx/2)$, 자식의 위치는 $2 * idx (+1)$ 로 구할 수 있다.

Binary Search Tree
---
- Binary Search Tree는 Binary Tree의 특수한 형태로, left child 는 parent 보다 더 작은 값을, right child는 parent 보다 더 큰 값을 갖도록 한다.
- Binary Search Tree의 특징 중 하나로는 중복된 값이 tree 내에 존재하지 않기 때문에 어떤 노드보다 동일한 값이 존재하는 것은 고려하지 않아도 된다.
- Binary Search Tree의 장점은 **평균적인 search 속도가 $O(log N)$** 으로 떨어진다는 것이다. 하지만, '평균'이기 때문에 insert 하는 순서에 따라서 **한쪽으로 skewed 된 경우 (최악의 경우) $O(N)$** 의 search / insert / delete 속도를 보인다. 이것을 `degenerate binary tree` 라고 부르고 internal node가 오직 하나의 자식 노드만 갖는 경우라고 정의한다*
- 이러한 문제점을 해결하기 위해서 `self-balancing binary tree` 가 나온다. self-balancing tree 는 tree 의 한 종류로 한쪽으로 skewed 된 tree 를 $O(log N($) 의 속도로 search / insert / delete 할 수 있도록 알아서 skewness를 조절을 해주는 tree 다.
- 대표적으로는 `AVL Tree` 가 있다. AVL Tree 는 balance factor 를 사용하는데, balance factor 는 다음을 만족한다.
> $balance\ factor = |H_l - H_r| \leq 1\ (l: left\ subtree, r: right\ subtree, H: height)$
- 즉, 왼쪽 sub tree의 높이 - 오른쪽 sub tree의 높이 (또는 그 반대) 의 차이를 balance factor라고 하는데, balance factor는 항상 [1, 0, -1] 중 하나의 값을 갖게 하도록 하는 것이 AVL Tree 의 특징이다. 그러면 어떻게 AVL Tree 는 self-balancing 을 할 수 있을까. 다음의 4가지 경우에 따라서 balancing을 한다.
- LL -> Right Rotation
- RR -> Left Rotation
- LR -> Left Rotation, Right Rotation
- RL -> RIght Rotation Left Rotation

[AVL Tree Rotations](https://www.youtube.com/watch?v=_nyt5QYel3Q)

Red Black Tree
---
- Red Black Tree는 가장 널리 사용되는 self-balancing binary search tree 인데, Java 의 HashMap 도 Red Black Tree 로 구현되었다고 한다. 또한, C++ 의 map 도 Red Black Tree로 구현되었는데, 좀더 구체적으로 말하자면 Hash 테이블의 키 중복으로 발생하는 문제를 해결하기 위한 collision resolution의 한 방법으로 closed addressing 을 사용할 수 있는데, closed addressing 에서 separate chaining 의 구현 방법으로 볼 수 있다. 뒤에서 다루겠지만, separate chaining 을 구현하는 방법은 두 가지가 있다. 1) Linked List 2) Binary Search Tree. 여기서 2) 에 해당하는 것을 구현할 때, Red Black Tree를 사용한다.
- Red Black Tree는 몇가지 조건과 2가지 동작을 생각하면 된다.
#### 1. 조건
- 모든 노드는 red 또는 black 색깔을 갖는다.
- 루트 노드는 항상 black 색깔을 갖는다.
- 새로운 노드는 항상 red 색깔을 갖는다.
- red 노드의 부모는 항상 black 이어야 한다. 이는 `double red` 문제를 허용하지 않는다는 말과 같다.
- leaf node는 항상 black 노드 (NIL)를 자식 노드로 갖는다고 생각한다.
- 모든 leaf node에서 root node 까지 이르는 가장 짧은 경로에 있는 black node 의 개수는 항상 같다.

#### 2. 동작
- 먼저 red 색깔을 갖는 노드를 삽입한다. 그 다음 double red 문제가 발생하는지 확인을 하는데, 문제가 발생하는 경우 uncle node (부모의 형제 노드) 의 색깔을 보고 다음 2가지 동작 중에 어떤 것을 선택할지 판단한다.
- uncle이 black인 경우: Restructuring
- Restructuring은 트리를 재구성하는 것이다. 먼저, 삽입된 노드를 N 이라고 하고, 부모 노드를 P, 조부모 노드를 G라고 하자. 각 노드들을 정렬하여 중간에 있는 노드를 선택한다. 이렇게 선택된 노드를 부모 노드로 하고 나머지 노드를 자식 노드로 만든다.
- uncle이 red인 경우: Recoloring
- Recoloring 은 삽입한 노드의 부모 노드와 uncle 노드의 색을 black 색깔로 칠해버리는 것이다. 그리고 조부모 노드는 색을 red로 칠해버린다. 하지만 Recoloring 을 한 다음에도 여전히 dobule red 문제가 발생할 수 있기 때문에 - 정확히 말하면, 조부모 노드에서 다시 double red 문제가 발생할 수 있음 - 다시 문제가 발생한 노드에서 uncle node 를 보고 restructuring 을 할지 recoloring 을 할지 판단할 수 있다. 또한, double black 이라는 문제는 없기 때문에 자식과 부모 노드가 모두 black 인 것은 문제가 되지 않는다.

[Restructuring](https://nesoy.github.io/articles/2018-08/Algorithm-RedblackTree)
[Recoloring](https://nesoy.github.io/articles/2018-08/Algorithm-RedblackTree)

#### 3. 시간복잡도
- Restructuring 수행하는데는 $O(1)$ 상수시간 만큼 걸리지만, leaf 에 추가하는데 $O(log N)$ 만큼의 시간이 걸림.
- Recoloring 수행하는데는 $O(1)$ 상수시간만큼 걸리지만, root 까지 propagate 하는데 $O(log N)$ 만큼의 시간이 걸림.

기타
---
- Binary Search Tree 를 공부하다보니 자연스럽게 **Java 의 HashMap**에 대한 얘기가 나와서 몇 자 적어본다. HashMap (C++ 에서는 map)은 <key, value>를 저장하는데, 나는 separate chaining 을 구현할 때, 모두 Linked List 로 구현하는 줄 알았다. 그런데 생각해보니 꼭 Linked List 일 필요는 없는 것이다. 만약에 더 빠른 탐색 속도를 원한다면 Binary Search Tree 로도 구현할 수 있는 옵션이 있는 것이다. 난 Java가 주언어가 아니기 때문에 매우 딴소리일 수 있지만, **Java 1.8 이후 HashMap 에서는 8개 미만의 데이터에 대해서는 separate chaining에서 Linked List 를 사용하고, 8개 이상인 데이터에 대해서는 Red Black Tree로 변환해서 사용한다고 한다.**
- 이건 HashMap 의 경우만 해당되지 않는다. HashSet 이라는 것도 있는데, Set 데이터를 저장할 때 Hash Table 을 사용해서 저장하는 것이 HashSet 이다. 그런데, TreeSet, LinkedListHashSet 이라는게 또 있단다. LinkedListHashSet 은 Hash table 을 사용하는 것은 맞는데, 데이터를 삽입한 순서를 기억하기 위해서 사용하는 자료구조이고, TreeSet 은 Set 이긴 한데 데이터를 정렬된 상태로 저장하기 위해서 사용한다고 한다. **아니나 다를까, TreeSet 또한 Red Black Tree 로 구현되어 있다고 한다.**
- 이런 걸 보면서 느끼는 점은, 데이터를 저장할 때 목적에 맞는 자료구조를 사용하는 것이 생각보다 더 디테일한 부분에서까지 구현되어 있다는 것이다. 예를 들어, Set은 그냥 중복되지 않은 값을 저장할 때 사용한다고 생각했는데, 여기서 정렬이 필요하면 Tree를 사용하고, 삽입 순서가 고려되어야 하면 Linked List를 사용한다는 점이 인상깊었다. **나중에 어떤 문제를 맞닥뜨렸을 때, 정렬이 된 상태로 저장이 되어있어야 하는 것인지, 그렇게 되면 Tree 를 쓰는게 유용할지 등에 대해서 항상 고려해보는 습관을 갖는 것이 중요할 것 같다.**

Google Interview
---
- Binary Search Tree 의 활용 사례는?
- Red Black Tree. Red Black Tree 는 Java 의 HashMap 이나 C++ 의 map 자료구조를 구현할 때 널리 사용되는 Binary Search Tree 이다. 정렬된 데이터를 Tree 형태로 저장하는 자료구조에서 종종 사용된다고 볼 수 있다.