binary search tree
- parent is greater than left child
- right child is greater and equal to the parent
- ex. 6 /
4 7 / \ /
3 5 6 8
문제 특징: while문 사용한다.
time complexity average - O(log n) -> 한 노드당 선택지 2개, 내려갈때마다 1/2이니까. (if valanced binary search tree 일때만) worst case - O(N) -> 트리가 한쪽으로 쏠려있는 경우에.
binary tree
-
순회순서종류
in-order
pre-order
post-order
DFS(Depth Forth Search), BFS(Breadth First Search) left child, right child 가 있는것. 안에 어떤 숫자가 들어가도 상관없다. -
in-order : left-right-parent 순서로 조회. => 왼쪽 가장 마지막 노드 일때까지 깊게 visit. => right로 이동. 가장 깊게 visit => parent
-
대부분 많은 경우에 in-order + dfs로 하면 풀 수 있는 문제들이 빈번하기때문에 순서 이해 및 재귀 의미도 빠삭하게 알고 있어야 한다.
depth == top to bottom approach, height == bottom to up approach binary tree 문제를 풀때 두가지 중에 선택함에 따라 해석이 아예 달라짐. 특히 트리 및 그래프 문제에서.
height는 가장 끝 leaf node(자식 왼, 오 node가 둘 다 없는 노드)에서의 기준으로 삼는다. depth는 root 기준으로 +1, height 는 leaf node 를 기준으로 +1 하되 left node vs right node 중 큰 숫자 +1 값이 parent의 height이 됨.
recursion (재귀)
- recursion call stack
- 추후 내용 추가.
time complexity O(N) : 특정 node를 찾기위해 트리 모든 노드를 봐야할 수 있기 때문이다. 여기서 N이란, 어떤한 input이 들어오더라도 치환 가능한 값. (total number of nodes in the tree.)