Mikyo CodingStory

안녕하세요. 밀쿄입니다. 오늘은 이진 탐색 트리에 대해서 알아보겠습니다. 이진 탐색트리는 두 자료구조를 결합한 자료 구조 입니다. 그 자료 구조 중 하나는 탐색이 빠르지만 삽입 삭제가 안되고 다른 하나는 삽입 삭제는 빠르지만 탐색에 O(n)이란 복잡성을 가지고 있습니다. 그래서 그 두개를 합쳐서 탐색이 빠르고 삽입삭제가 빠른걸 만들고자 고안이 되었습니다. 그래서 그 두 개가 무엇인지 궁금하실텐데 바로 이진 트리와 연결리스트입니다. 자 그럼 이진 탐색 트리에 대해 본격적으로 알아보겠습니다 이진 탐색트리는 다음과 같은 특징을 가지고 있습니다. 각 노드의 왼쪽 서브트리에 있는 노드의 값은 부모 노드보다 그 값이 작다. 각 노드의 오른쪽 서브트리에 있는 노드의 값은 부모 노드보다 그 값이 크다 들어가기전에 스위..

안녕하세요 밀쿄 입니다. 오늘은 잡담없이 바로 시작합니다. 오늘은 원형큐라는 걸 갖고왔습니다 조금 어렵지만 금방 이해하실꺼라 믿습니다. 바로 원리부터 들어가보도록 하죠. 자 여기 손그림이 아니라 큐가 있습니다. Read포인터랑 write포인터가 있습니다 이 상태에서 write가 되면 이렇게 write가 증가합니다. 여기서 하나더 들어오면 아래 그림처럼 하나 더 늘어나겠죠? 여기서 이제 read를 하면.. 이렇게 됩니다 Read가 하나 늘어나죠. 이렇게 가다가.. 큐가 다차면 write가 처음으로 돌아와서 오버라이드 합니다. 이렇게 가득차면 처음으로 돌아와서 원형버퍼 ,링버퍼, 뭐 그렇게 부릅니다. 참고로 저렇기 때문에 크기가 한정적입니다. (반대로 애기하면 크기를 모르면 못 쓰겠네요 ) 이걸 응용해서 큐..