Binary Search Tree, BST (이진 탐색 트리)

이진 트리에서는 하나의 Node 가 1개의 key(data) 와 2개의 자식 node 를 가리키는 link(left,right) 를 가지고있습니다. BST(이진 탐색 트리)는 검색, 삽입, 삭제은 평균 O(log n) 의 시간 복잡도를 가집니다. 하지만 최악의 경우 편향이진트리(구글 이미지 검색) 생성되면 최악의 효율O(n)이 발생합니다. 이를 보완하고 좌우 균형을 맞추어 탐색 효율을 목적으로 B tree라는 것을 사용합니다.

아래의 java 소스코드는 해외 블로그를 참고하였습니다. 탐색,삽입 하는 코드는 비교적 간결하고, 트리의 node 를 삭제하는 logic 은 3가지로 분류 됩니다.

1. 삭제 node 의 자식이 없는 경우 - node 를 바로 삭제 합니다.

2. 삭제 node 의 자식이 1개 인 경우 - 자식 node 를 자신 대신에 부모 node 의 자식 pointer 에 연결합니다. 그 이후에 node 를 삭제 합니다. node 를 그 자식 node 로 대체한다고 보면 좋을 것 같습니다.

3. 삭제 node 의 자식이 2개 인 경우 - left subtree 의 최대 node 나 right subtree 의 최소 node 를 가져와서 삭제할 node 를 대체 합니다. 그런데 여기서 최대 node나 최소 node 가 하나의 자식 node 를 가질 경우 그 자식 node 를 조부모 node 와 연결하는 logic(소스코드의 getSuccessor 함수) 이 추가되어야합니다.

참고 문서 - 이진탐색트리(java)