The best case, O(1), of searching in a BST, regardless of the size of the tree, would be if the data we searched for is at the root node. AVG: O(log n) worst: O(n) ADD 1. data 를 찾을시 search 는 성공하지만 add 는 추가하지 않는다(이미 있으니까) 2. node 가 null, 즉 비어있으면 search는 실패하지만 add 는 그곳에 데이터를 추가한다 ## child 가 null 인걸 확인하고 add 하는것이지 null node 까지 직접 가지는 않는다 curr = null 로 base case 확인, 데이터가 없을수 있으니까 data 가 현재 curr 보다 작..

일단 tree 를 공부하기 전에 항상 물어야할 질문이 있다. "왜 써야하는가?" tree 는 이 녀석들이 하지 못하던 searching 을 빠르게 만들어준다. root = 맨 꼭대기 의 수, tree 의 "왕" internal node = child 가 있는 node, external nodes = child 가 없는 node (leaf 라고도 불린다) 이번 시간에는 binary tree 안에 속해있는 Binary Search Trees 라는 귀여운 녀석이 있는데 이녀석을 탐구해볼 생각이다. 줄여서 BST, 이녀석이 되려면 총 3가지 조건이 필요하다. 1. 자식이 둘까지만 가능하다. 3명 이상인 다자녀 집안은 취급하지 않는것 같다. 2. children은 left, right 로 label 되어야 한다...