ITeus

Win Tree는 Binary Tree의 일종으로, Leaf Node끼리 비교 후 작은값이 승자로 부모노드가 되는 Tree입니다. Heap과 유사해 보이지만, 실질적으로 Distinct한 Element는 Leaf Node만큼만 있다는 것을 알 수 있습니다. 이때, 각 Leaf Node에 이미 Sort된 List를 연결하면, 다수의 List를 하나로 정렬하는 것이 가능합니다. 이제, Win Tree에서 Top Node에 위치한 값을 Orderd List에 넣고, 해당 Leaf Node의 다음 값을 가지고 옵니다. 이런 방식으로 모든 List가 Empty가 될 때 까지 반복을 진행하면, Leaf Node에 붙어있던 모든 List가 하나로 통합된 Ordered List로 통합되게 됩니다. 각 Element를 ..

Heap은 Binary Tree를 활용한 응용된 Tree계열의 자료구조 입니다. Left부터 채워넣은 완전 이진Tree이며, 상위 Node로 갈 수록 Max Or Min 값을 보여주는 Tree입니다. 이때 Max_heap과 Min_heap이 있으며, 아래 예시를 보면 이해하기 쉽습니다. Random한 Array를 Max Heap 또는 Min Heap을 만들었을 경우의 모습입니다. 따로 설명이 필요없어보이네요 이때 Tree구조를 언어에서 표현하는 방법으로 Pointer 방식과 List 방식이 있는데, List 방식으로 구현하도록 하겠습니다. List로 구현할 경우, i번째의 Node는 2i+1, 2i+2번째 노드의 부모Node가 됩니다. (Ex, 위의 1번째 Node는 3, 4번째 Node의 부모Node임..

이진Tree는 Tree구조 중 Node가 Left와 Right만 갖는 Tree를 의미합니다. Tree에 대한설명은.... (추후 Tree 페이지 추가후 삽입예정입니다) Binary Tree는 각 Node마다 Left, Right를 구분하며, Left 와 Right는 각각 다른 Node를 Pointing하는 구조를 가지고 있습니다. 이때 Node C처럼 Left와 Right가 모두 빈 Node를 Leaf Node라고 합니다. 이러한 이진 Tree를 구현하는 방법은 Array를 이용한 구현 방법과, Node를 이용한 구현방법이 있습니다. 두가지 방법 모두 Tree를 구현할 수 있지만, 완전 이진 Tree가 아니면 Array를 활용할 경우 불필요한 Memory가 사용됩니다 이러한 Binary Tree는 Bin..

연결List에 대해서 포스팅하면서, 단일연결List는 Next Index의 접근은 용이하지만, 이전 Index로 가는것은 어렵다고 했습니다. 이러한 문제점을 개선하기 위해서 고안된 개선된 Connect List중 원형연결 List, 이중연결 List가 있습니다. 1. 원형연결 List 기존 단일연결list의 마지막 Index의 Node는 항상 Next Node가 Null값을 갖게 됩니다. 이때 Data의 여부를 Search할 경우, 지속적으로 "Next Node가 Null인가?" 를 검사하게 됩니다. 하지만 마지막 Index의 Node를 첫번째 Index Node를 Pointing 하게 함 으로써 프로그램의 성능 향상을 도모할 수 있습니다. 파이썬으로 구현된 원형 연결 List입니다. class node..

일반적인 Array가 있다고 해봅시다. 일반적으로 Array의 순서는 메모리의 물리적인 순서와 동일합니다. 이때, Array 중간에 Element을 삽입하기 위해선 삽입된 위치 이후는 전부 이동을 해 줘야합니다. 연결리스트는 중간에 Element를 삽입할 때 발생하는 Memory의 읽기/쓰기를 최소화 하는 자료구조입니다. Node를 생성하고, 해당 Node의 Next Node를 Pointing 하게하는 자료구조 입니다. 위 이미지를 보면 알수있지만, 연결List의 순서는 Mem주소의 물리적인 순서와 무관합니다! 덕분에 연결List를 활용할 경우, Element의 삭제 & 추가에 따른 Memory 읽기/쓰기를 최소화 할 수 있습니다. 추상화된 이미지를 보면, 마치 전화선 연결하는 것 처럼 서로의 연결을 바..

지난시간에 Queue 자료구조는 Data를 지울 경우 Queue의 Max Capacity가 감소한다고 했습니다. teus-kiwiee.tistory.com/24 Queue Queue는 Array를 활용한 사용자 자료구조 중 하나입니다. Queue의 원리는 First In First Out(FIFP) 가장 먼저 들어온 Element가 가장 먼저 나간다 입니다. 정수기의 종이컵 / 놀이공원 대기열을 생각하면 쉽습 teus-kiwiee.tistory.com Circular Queue는 이러한 단점을 극복하기 위해서 고안된 특이한 Case의 Queue라고 할 수 있습니다. 원형Queue는 선형Queue의 Input과 Output이 서로 붙어있는 구조라고 할 수 있습니다. 이렇게되면 FIFP의 원칙을 유지하되, ..