1일1코딩

CS/자료구조

[자료구조] Binary Search Tree _ 이진 탐색 트리

Binary Search Tree 1) 데이터 특징: Left Child의 key값은 parent보다 작고, Right Child의 key 값은 parent보다 큼. 2) 형태적 특징: Binary Tree - Inorder Traversal of BST = 오름차순 sort Searching – Recursive ver. Searching – Iterative ver. Searching BST의 시간 복잡도 - Average case: O(h), h=height of tree - Worst case: O(n), n=number of nodes Insertion BST의 시간복잡도 - O(h), h=height of tree Insertion (1) Insertion (2) – Modified Searc..