이진 탐색 트리의 정의?
-
트리 형태의 자료 구조
-
왼쪽 서브 트리와 오른쪽 서브 트리를 가짐
-
루트 노드는 왼쪽 서브 트리의 모든 노드들보다 큼
-
루트 노드는 오른쪽 서브 트리의 모든 노드들보다 작음
이진 탐색 트리의 특징?
-
거치는 노드들에 의해 특정 노드의 값의 범위가 정해질 수 있음
-
전위 순회, 중위 순회, 후위 순회로 모든 노드들을 탐색할 수 있음
-
순회의 기준은 루트 노드임
-
리버스 중위 순회로 값의 내림 차순 순으로 방문할 수 있음
이진 탐색 트리의 탐색, 삽입, 삭제?
-
이진 탐색 트리는 탐색, 삽입, 삭제에 O(logN)의 시간을 가짐
-
탐색은 루트 노드를 기준으로 왼쪽 서브 트리 혹은 오른쪽 서브 트리로 이동함
-
삽입하기 위해서 탐색을 이용하면, 삽입될 노드의 위치를 찾을 수 있음
-
탐색으로 삭제할 노드를 찾은 다음에, 왼쪽 서브 트리 혹은 오른쪽 서브 트리로 대체
이진 탐색 트리의 활용?
-
해쉬의 B+Tree, B-Tree가 존재
-
B+Tree는 내부 노드에서 키만 갖고 있기 때문에, 더 많은 키를 담을 수 있어서 트리의 높이를 낮출 수 있음
-
B-Tree는 내부 노드에서 키와 데이터를 동시에 갖고 있기 때문에 B+Tree보다 트리의 높이가 높음
-
B+Tree는 리프 노드에 데이터가 있기 때문에, 데이터를 찾으려면 리프 노드까지 도달해야 함
