이진탐색트리란?
이진탐색의 개념을 트리 형태의 구조에 접목한 자료구조
정렬된 데이터 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어가며 특정항목을 찾는 탐색방법
이진탐색 트리에서의 삭제
삭제하려는 노드의 자식 수에 따라
자식노드가 없는 노드(리프 노드) 삭제 : 해당 노드를 단순히 삭제한다.
자식노드가 1개인 노드 삭제 : 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다.
자식노드가 2개인 노드 삭제 : 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.
삽입
삽입을 하기 전, 검색을 수행한다.
트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.
Recording...