목록BST (1)

그냥 블로그

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

이진 탐색 트리란?이진탐색을 위한 이진트리.모든 노드의 Key는 유일하다. (중복 없음)왼쪽 자식은 나보다 작다오른쪽 자식은 나보다 크다 이진 탐색 트리의 장점 일반 이진 탐색은 중앙 요소를 알아야하기 때문에 "배열"에서만 사용 가능. 연결 리스트는 이진 탐색에 적합하지 않다. 배열의 크기가 변화면 안되는 정적 이진 탐색 트리 배열을 사용해 탐색할 때보다 시간 복잡도가 작다 O(logN) 동적으로 데이터 집합 크기가 바뀌고 순서가 바뀌어도 문제가 없다. 주의할 점트리 모양이 한쪽으로 치우치면 트리 탐색의 장점인 O(logN) 시간복잡도가 마치 배열을 순차 탐색하는 듯하는 O(N)에 가까워지게 된다. => 데이터를 추가/삭제 할 때 트리 모양을 균형있게 만드는 "레드 블랙 트리"가 있다. (C++ map ..
C++/알고리즘 개념 2024. 2. 22. 20:11
이전 Prev 1 Next 다음