coding/Data Structure(C)
2020. 12. 13.
[C] 이진탐색트리(BST; Binary Search Tree)
이진탐색트리를 구현해보자. 이진탐색트리는 이진트리 기반의 탐색을 위한 자료구조이다. 효율적인 탐색을 위해 inorder traversal(중위순회) 방법을 씀. 이러면 자료가 오름차순으로 정렬되어서 시간복잡도를 줄일 수 있다고 한다. 최선의 경우 최악의 경우 이진트리가 균형적으로 생성되어 있는 경우 : h=log(n) 경사 이진트리(일렬로 쭉 늘어선 트리) : h=n 시간복잡도: O(log(n)) 시간복잡도: O(n) [C]트리와 이진트리 포스트에서 이진트리의 성질 부분을 다시 복습하자. n개의 노드를 가진 이진트리의 높이는 최대 n이거나 최소 [log(n+1)]이 된다. 왜 log(n+1)에서 log(n)이 됐는지는 모르겠지만..? 아마 Big-O 기법이 뭉뚱그려서 최고순위 차수만 고려해서(?) 그런가..
![[C] 이진탐색트리(BST; Binary Search Tree)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/bgQeSz/btqP11hc0lU/NDKEQfoyiYCmGmfdGONhG0/img.png)