[자료구조] 트리 (tree)

current와 parent의 라임 속에서 허덕이는 자료구조입니다. 

1. 용어

▶ Node 노드: 트리에서 데이터를 저장하는 기본 요소 + 연결된 다른 노트에 대한 branch 정보
▶ edge = branch: 노드를 연결하는 선
▶ Root node: 트리의 가장 위에 있는 노드
▶ Parent node: 위아래로 연결되어 있는 두 개의 노드 중 위에 있는 노드
▶ Child node: 위아래로 연결되어 있는 두 개의 노드 중 아래에 있는 노드
▶ Leaf Node (terminal node): childe node가 없는 노드
▶ Level: Root node로부터 하위 branch로 연결된 노드의 길이 (root node: level 0)
▶ Depth 깊이: Root node로부터 노드까지 거쳐야하는 branch의 개수

트리는 Node와 Branch를 이용해서 사이클을 이루지 않도록 구성된 구조입니다. 
한 노트가 여러 노드를 가리킬 수 있는 비선형적 자료구조이며, 데이터 구조의 계층적인 속성을 표현할 수 있습니다. 

2. 이진 트리와 이진 탐색 트리 

두 단어를 거의 동의어로 많이들 사용하는 것 같지만 구별이 필요한 용어입니다. 
▶ Binary tree 이진 트리: 노드의 최대 branch가 2인 트리
▶ Binary search tree 이진 탐색 트리: 노드의 왼쪽 sub-tree는 root node보다 작은 값, 오른쪽 sub-tree에는 root node보다 큰 값인 트리이며 각 sub-tree들은 다시 이진 탐색 트리를 이루는 구조 

3.이진 탐색 트리의 장/단점

장점: 배열에 비해 탐색 속도가 빠르다

출처: t.ly/A6Si

시간복잡도: $O(h)$ (*밑이 2) , h = 트리의 depth 

단점: 최선의 경우, 즉 균형잡힌 트리의 경우에는 시간복잡도가 $O(logn)$ 이지만
최악의 경우 (e.g 1~10까지의 정수 데이터의 root node를 1로 지정하는 경우) 링크드리스트와 같다

4. BST 구현 (by linked list)

You can watch practicing notebook file on Github

node 삭제에 대한 부연 설명

Node를 삭제할 때는 해당 노드의 child node 개수에 따라 코드가 달라집니다. 
lead node 일 경우, child node가 1개일 경우, child node가 2개일 경우로 나뉘는데, child node가 2개인데다가 오른쪽에 있는 경우가 많이 헷갈려서 아래와 같이 그려보았습니다. 
 case1은 검정색 트리의 경우 6을 삭제할 때, case2는 주황색 노드까지 가지고 있는 트리의 경우 6을 삭제할 때입니다. 
 핵심은 1) 삭제할 노드의 child node 중 가장 작은 값을 가진 node(=change node)를 찾기, 2) 삭제할 노드의 parent node를 change node에 연결하기, 3) 삭제할 노드의 left&right node를 change node의 left&right로 연결해주기 입니다.