이진검색트리 (Binary Search Tree) (정리중,,,,,,)

# 이진검색트리 (Binary Search Tree) 개념

- 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조

- 데이터는 정렬이 되어 있어야하며, 탐색 작업에 효율적

- 한 노드에 자식이 최대 2개까지만 존재할 수 있는 트리

1. 모든 노드의 키는 유일하다. 

  - 중복된 데이터를 갖는 노드가 없다는 뜻이다. 

  - 여기서 키의 의미는 노드 안에 들어 있는 데이터 값을 의미한다.

2. 왼쪽 서브 트리의 키들은 루트의  키보다 작다. 

  - 예를 들어 루트노드의 데이터가 5라고 하면, 왼쪽 서브트리에는 무조건 5보다 작은 값들만 존재해야 한다.

3. 오른쪽 서브 트리의 키들은 루트의 키보다 크다.  

  - 위와 같은 원리로 오른쪽에는 루트의 데이터 값보다 더 큰 값들만 존재한다.

4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 

  - 순환적으로 정의되었다는 뜻이다.

  - 즉 왼쪽 서브트리로 내려가든, 오른쪽 서브트리로 내려가든 동일한 법칙이 적용된다는 뜻이다.

# 이진검색트리 (Binary Search Tree) 예시

- 전화번호부에서 전화번호를 찾거나 

- 서점에서 책을 찾거나 

- 지도에서 목적지를 찾는것

# 이진검색트리 (Binary Search Tree) 목적

- 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능합니다.

- 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만 

  탐색하는 데에는 O(n)의 계산복잡성이 발생합니다.

- 이진탐색트리 핵심 연산인 탐색, 삽입, 삭제의 계산복잡성은 모두 O(h) 입니다.

# 이진검색트리 (Binary Search Tree) 용어

successor: 삭제 대상 노드의 오른쪽 서브트리 가운데 최소값

redecessor: 삭제 대상 노드의 왼쪽 서브트리 가운데 최대값

# 시간복잡도 정리

삽입, 삭제, 탐색 모두 최선의 경우(트리의 균형이 잘 잡혀있는 경우, 즉, 왼쪽 오른쪽 자식이 잘 분배되어 있는 경우) O(logN)의 시간복잡도를 가지고, 최악의 경우 (자식 노드가 한쪽으로 쏠려 있는 경우) O(N)이다.

최악의 경우에는 경우에는 균형잡힌 이진 검색트리(balanced binary search tree)으로 사용하면 좋다.

# Binary Searh Tree의 3가지 순회방법

참고 강의: https://www.youtube.com/watch?v=QN1rZYX6QaA&index=2&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP

- Inorder (Left -> Root -> Right)

- Preorder (Root -> Left -> Right)

- Postorder (Left -> Right -> Root)

# 이진검색트리 (Binary Search Tree) 정리

- array와 비교시 tree는 add/remove 연산 속도가 빠르다.

- balanced binary search tree의 경우 insert/delete가 O(log N)이다. (자바에서 TreeMap으로 구현)

# 유투브 영상

https://www.youtube.com/watch?v=9ZZbA2iPjtM&t=3s

https://www.youtube.com/watch?v=9ZZbA2iPjtM&index=8&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP

# 참고사이트

★★https://kingpodo.tistory.com/29

★★http://ivis.kr/images/a/a5/2018_DS_ch09.pdf

★★https://songeunjung92.tistory.com/31

★★https://swalloow.tistory.com/35

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

https://wkdtjsgur100.github.io/binary-search-tree/

https://mattlee.tistory.com/30

https://kka7.tistory.com/78