이진 탐색 트리의 가장 왼쪽에 존재 → 모든 노드는 자신의 왼쪽에 자신보다 작은 값을 가져야 하기 때문이다.
트리의 가장 오른쪽에 존재 → 모든 노드는 자신의 오른쪽에 자신보다 큰 값을 가지기 때문이다.
순회란? 모든 노드들을 한번씩 방문하는 것을 의미한다.
중위 순회 (inorder traversal)
루트 노드를 기준으로 왼쪽 서브 트리로 가다가 더 이상 왼쪽 서브트리가 없으면 현재 노드를 방문해서 처리할 일들을 처리한 후 그 노드의 오른쪽 서브트리로 간다. 오른쪽 서브트리가 없다면 루트 트리로 이동 후 다시 중위 순회를 한다.
위의 출력 순서를 보면 1 → 5 → 6 → 10 → 14 → 17 → 21
이진 탐색 트리의 값들을 순서대로 방문을 한다는 특징이 있다.
해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드
해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드
이진 검색 트리를 생성하기 위해 노드를 추가할 때 쓸 insert
함수
삭제하려는 노드가 있는지 검색 → 있으면 삭제
결국 삭제가 검색을 동반한다. 삭제를 알면 자연스럽게 검색이 이해된다.
delete(20)
삭제될 노드를 가리키던 레퍼런스를 가리키는 것이 없도록 처리
delete(30)
삭제될 노드를 가리키던 레퍼런스를 삭제될 노드의 자녀를 가리키게 변경
삭제될 노드의 오른쪽 서브 트리에서 제일 값이 작은 노드가 삭제될 노드를 대체한다.
위의 상태에서 85를 추가하고 70을 삭제한다면
add(85)
delete(70)
중요한 것은 삭제가 되더라도 이진 탐색트리의 특징이 유지돼야 한다는 것이다.