자료구조) Tree - Binary Search Tree, Segment Tree, Binary Indexed Tree

Binary Search Tree (이진 탐색 트리)

def

• 모든 원소는 서로다른 유일한 값.

• 왼쪽 subtree의 값은 그 root보다 작다.

• 오른쪽 subtree의 값은 그 root보다 크다.

• 왼/오른쪽 subtree도 Binary Search Tree이다.

• 탐색/삽입/삭제 중 삭제연산이 번거롭다. 노드를 삭제한 후에도 BST를 유지해야하므로 후속조치가 필요하다.

• 삭제할 노드가 1. degree=0(leaf node)인지 2. degree=1인지 3. degree=2인지에 따라 달라짐.

---

Segment Tree

구간의 정보를 빠르게 구할수있는, Complete Binary Tree 형태의 자료구조

Example) 구간 최소값을 구하는 Segment Tree
구하려는 데이터 배열을 완전이진트리의 최하단에 배치하고, 부모노드는 자식노드들중 가장 작은값을 갖게 구성하여 트리를 완성시킨다.

구간 최소값을 구하는 Segment Tree

세그먼트 트리 (Segment Tree) 참고

---

Binary Indexed Tree = fenwick Tree

Segment Tree와 비슷하게 구간의 정보를 저장할수있는 자료구조
구간 합 등을 알아내는데 이용된다.
Segment Tree보다 간단하지만, ST가 BIT보다 좀더 다양한 목적으로 사용가능하다.

• 8번지의 검정박스는, 8번지의 데이터가 1~8까지의 합을 축적하고있음을 의미
• 파란박스를 보면, 1은 1,2,4,8,16번지에 더해졌음을 의미
• 청록박스를 보면, 1~11번지까지의 합은 8,10,11번지의 합을 구하면 된다

펜윅 트리 (바이너리 인덱스 트리) 참고