이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree)

이진트리는 아래의 규칙을 가지고 있는 자료구조이다. 

• 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다.
• 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 
• 각각의 서브 트리도 이진 탐색 트리를 유지한다. 
• 중복된 키를 허용하지 않는다. 

 

특징

• 이진 탐색 트리 규칙에 의해 데이터가 정렬된다. 
• 이진 트리에 비해 탐색이 빠르다 (균형 유지)
  • 균형상태 복잡도 O(logN)
  • 불균형상태 복잡도 O(N)

왼쪽은 균형, 오른쪽은 불균형

이진 탐색 트리 - 삽입

• Root 부터 비교를 시작 한다(중복 키 발견 시 노드 추가하지 않고 종료 된다.)
• 삽입할 키가 현재 노드의 키보다 작으면 왼쪽으로 이동한다. 
• 삽입할 키다 현재 노드의 키보다 크면 오른쪽으로 이동한다. 
• Leaf 노드에 도달 후 데이터를 입력한다. 

이진 탐색 트리 - 삭제(1)

삭제 대상 노드가 Leaf인 경우

• 삭제 대상 노드 삭제 
• 부모 노드의 해당 자식 링크를 null로 변경

이진 탐색 트리 - 삭제(2)

삭제 대상 노드에 자식 노드가 하나가 있는 경우 

• 자식 노드를 삭제 대상 노드의 부모 노드에 연결
• 삭제 대상 노드 삭제

이진 탐색 트리 - 삭제(3)

삭제 대상 노드에 자식 노드가 둘인 경우

• case1 : 삭제 대상 노드의 왼쪽 서브트리에서 가장 큰 노드 선택 
• case2 : 삭제 대상 노드의 오른쪽 서브트리에서 가장 작은 노드 선택 
  • case1 or case2 에서 선택한 노드를 삭제 대상 노드 위치로 올림.
  • 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업을 수행
  • 삭제 대상 노드 삭제