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가지로 분류 됩니다. 삭제 node 의 자식이 없는 경우 - node 를 바로 삭제 합니다. 삭제 node 의 자식이 1개 인 경우 - 자..
Algorithm/Data Structure
2018. 4. 27. 11:20