이진 탐색 트리에 대해 설명해 주세요.
이진 탐색 트리는 이진 탐색과 연결 리스트가 결합된 자료구조로,부모 노드는 최대 두 개의 자식 노드를 가질 수 있다.
왼쪽 서브 트리의 모든 값은 부모 노드의 값보다 작고, 오른쪽 서브 트리의 모든 값은 부모 노드의 값보다 크다는 특징이 있다.
모든 원소는
Key를 가지며 키 값은unique하다.
꼬리 질문
이진 트리의 사용 방법
검색
루트 노드에서 시작해 키 값과 찾으려는 값을 비교한다.
찾으려는 값이 더 작으면 왼쪽, 더 크면 오른쪽 자식 노드로 이동한다.
같을 경우 검색에 성공한 것이며, 리프 노드에 도달할 떄까지 찾지 못하면 실패한 것이다.
삽입
기본적으로 검색과 동일한 과정으로 이루어진다.
검색에 실패하면 그 자리에 새로운 노드를 삽입한다.
삽입의 시간 복잡도는
O(트리의 높이)이다.삭제
삭제하려는 노드가 단말 노드인 경우
단말 노드의 부모 노드를 찾아서 연결을 끊는다.
삭제하려는 노드가 서브트리를 하나만 가지고 있는 경우
서브트리를 부모 노드에 붙여주고 노드를 삭제한다.
삭제하려는 노드가 두 개의 서브트리를 가지고 있는 경우
서브트리에서 삭제하려는 노드와 가장 비슷한 값을 가진 노드를 찾아 해당 위치로 옮긴다.
Last updated