이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 쉽게 알 수 있다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다 해도 트리의 높이는 30을 넘지 않기 때문이다. 😲
이진 트리의 경우에는 위치를 알고 있다면, 다시 말해서 데이터에 이르는 길을 알고 있다면 루트 노드에서부터 단말 노드에 이르기까지 총 30개의 노드를 지나는 과정에서 원하는 데이터를 찾을 수 있다. 물론 여기에는 다음과 같은 가정이 존재한다.
“이진 트리는 단말 노드에 이르는 길의 갈래가 매우 많다. 따라서 찾는 데이터가 존재하는 제대로 된 길을 선택할 수 있어야 한다.”
“이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.”
이진트리에 데이터의 저장 규칙을 더해놓은 것이 ‘이진 탐색 트리’이다. 이진 탐색 트리는 다음 조건들을 만족해야한다:
왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키
삽입은 간단하다 탐색 노드 보다 작을 경우 왼쪽 그렇지 않을 경우 오른쪽으로 내려가 자리를 찾으면 된다.
이진 탐색트리에서 임의의 노드를 삭제하는 경우, 삭제 후에도 이진 탐색 트리가 유지되도록 빈 자리를 채워야 한다.
노드를 삭제할 경우 3가지 상황이 있다:
삭제하고 그 부분을 NULL 로 만들어 주면 된다.