이진바이너리트리 (1) 썸네일형 리스트형 자료구조, Binary Search Tree 자료구조, Binary Search Tree Binary Search Tree 📌 BST란? 트리 자료구조의 한 종류 부모노드보다 작은 값은 왼쪽 자식 노드에, 부모노드보다 큰 값은 오른쪽 자식 노드에 저장하는 방식으로 데이터 저장 📌 장점 탐색, 삽입, 삭제 연산 시 시간복잡도 O(log n) 최대 2개의 자식 노드를 가지므로 이진 탐색 트리에서 데이터를 탐색할 때 절반 이하의 노드를 탐색한다. 데이터가 정렬된 상태를 유지하므로 중위순회(왼쪽서브노드 → 루트 → 오른쪽서브노드)하면 오름차순으로 정렬된 값을 얻을 수 있다. 📌 단점 이상적인 BST 모양이 아닐 경우(균형잡힌 이진 탐색트리) 경우, 시간 복잡도가 O(n)에 수렴한다. 이러한 최악의 경우를 피하기 위해, 데이터를 삽입할 때마다 트리의 균형을.. 이전 1 다음
