Tree (Tree란? Binary Search Tree란? Balanced tree란? - Red-black tree)
Tree 소개
Terminology
- Root node: 가장 상단의 node이며 parent node가 없음.
- Leaf node: 가장 하단에 위치한 node들이며 child node가 없음.
- Subtree: 중간 단계에서 특정 node 이하의 모든 node를 포함한 트리를 subtree라고 부름.
- Parent node: Root node를 제외한 node 들 중 child node를 가지고 있는 node들.
- Ancestor Node: Root node와 어떤 특정 node 사이에 끼어있는 node들.
- Key: node가 가지고 있는 값.
- Level: node의 층. Root node는 항상 level 1, 그 다음 층부터 ++.
트리 순회
- Pre-order traversal
- 현재 node를 먼저 방문. 그 다음 왼쪽 하위 node를, 그 후 오른쪽 하위 node를 재귀적으로 방문.
- In-order traversal
- 왼쪽 node를 먼저 방문, 그 다음 현재 node, 그 후 오른쪽 node 방문.
- Post-order traversal
- 두 자식 node를 먼저 방문, 그 후 현재 node 방문.
- Level-order traversal
- 트리의 맨 위 레벨부터 아래 레벨까지, 왼쪽에서 오른쪽 노드 순서로 방문.
BST (Binary Search Tree)
BST 특징
- 부모 노드의 값
왼쪽 자식 노드의 값 - 부모 노드보다 작거나 같은 모든 데이터 원소는 항상 왼쪽에 위치
- 부모 노드의 값
오른쪽 자식 노드의 값 - 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 위치
- 원소 검색을 할 때, 각 level마다 검색 범위가 절반으로 줄어듬.
- 즉, 트리의 모든 원소를 방문하지 않아도 됨.
- 트리의 높이
- 데이터 노드 검색 또는 삽입 동작
BST 원소 삽입
- 그냥 downstream으로 추가하면 됨
BST 원소 삭제
- node 삭제 후에도 BST 속성을 만족하도록 기존의 하위단 node를 끌어올려와야함.
- 삭제할 node에게
- child node가 없으면 그냥 지움
- child node가 1개면 자리를 계승시킴.
- child node가 2개면 현재 삭제하는 node보다 더 큰 숫자의 node가 자리를 계승함.
Balanced tree (AVL, red-black tree)
BST 의 단점
- 데이터가 sort된 상태에서 가장 작은 숫자를 root node로 만들고, 그 후 작은 순서대로 insert를 하게 된다면, 한쪽으로 치우쳐진 tree가 생길 것이다.
- 비슷한 예제로, 역방향 sort + 가장 큰 숫자를 root node로 만듬 + 큰 순서대로 insert를 하면 역시 또 한쪽으로 치우쳐진 tree가 생긴다.
find()
함수의 시간 복잡도는이다. - 그렇기에 tree의 높이는 최적화 되야한다.
- 이 작업을 ‘balancing’이라고 한다.
- 이 작업을 자동으로 하면 ‘self-balancing’이 된다.
- self-balancing tree의 종류에는 AVL tree와 red-black tree가 있다.
std::map
이 red-black tree 형태로 구현되어있다.- 왜 red-black tree로 되어있을까?
- AVL tree의 rebalancing rotation은
- Red-black tree의 rebalancing rotation은
이다. - “Why is std::map implemented as a red-black tree?”
- AVL tree의 rebalancing rotation은