이진트리탐색 (Binary Search Tree) 알고리즘

 ✅ 이진 탐색 트리

탐색 작업을 효율적으로 하기 위한 자료 구조

• 모든 노드의 데이터가 서로 다른 이진 트리
• 어느 노드에게 자식이 있는 경우
  • 왼쪽 자식의 데이터는 부모보다 작다
  • 오른쪽 자식의 데이터는 부모보다 크다

루드 노드 기준으로

• 왼쪽 서브 트리의 모든 데이터는 루트 노드보다 작다.
• 오른쪽 서브 트리의 모든 데이터는 루트 노드보다 크다.
• 중위 순회 할 경우, 오름차순 정렬된 데이터를 얻을 수 있다.

 

✅ 탐색

• 루트 노드와 탐색데이터를 비교
• 데이터가 더 작을 경우 왼쪽 서브트리로 (6과 12를 비교)O(h) ~ O(logn)
• 데이터가 더 클 경우 오른 쪽 서브트리로
• 편향 이진트리의 경우 O(n)

 

✅ 삽입

• 탐색 과정을 따라간다.
• 탐색에 성공할 경우 삽입 불가
• 탐색에 실패하는 시점에 새로운 노드로 데이터 추가

 

✅ 삭제

• 삭제할 데이터를 가진 노드를 탐색
• 삭제할 노드가 단말 노드면 삭제 (링크 해제)
• 삭제할 노드에 자식이 하나일 경우 부모와 대신 연결
• 자식이 두개일 경우, 왼쪽 서브 트리의 값 중 제일 큰 노드
• 오른쪽 서브트리의 값 중 제일 작은 노드 중 하나와 교체

---

✅ 노드로 이진 탐색 트리 구현하기

• insert()데이터를 BST에 추가(삽입)
• serch() 어떤 데이터가 BST에 존재하는지 판단(탐색)
• delete()데이터를 BST에서 제거(삭제)

 

구현 코드

• insert()

• serch()

• delete()

 

 

---