이진 트리에서는 하나의 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개 인 경우 - 자..
유클리드 호제법 2개의 수의 최소 공약수를 계산할 때 큰 수(a)를 작은 수(b)로 나누고, 나머지(r)가 0이 아니면 나누었던 수(b)를 나머지(r)로 다시 나누고 나머지가 0이 될때까지 반복합니다. 반복 하다가 나머지가 0이 될때 나눈 수가 최소 공약수가 됩니다. 예를 들어 78696과 19332의 최대공약수를 구하면, 78696 = 19332×4 + 1368 19332 = 1368×14 + 180 1368 = 180×7 + 108 180 = 108×1 + 72 108 = 72×1 + 36 72 = 36×2 36이 최소 공배수입니다. 최대 공약수(gcd, greatest common divisor) 최대 공약수를 계산하는 여러가지 방법이 있겠지만 유클리드 호제법 을 사용하여 계산하는 것이 코드도 간결..