Dog foot print

기존에 만들어서 올린 완전이진트리는 node타입이 마지막 삽입을 위한 노드에 대한 정보를 가진 링크가 더 있어서 구조체가 최소화 되지 못했다고 생각한다. 그래서 기존에 만든 완전이진트리의 노드는 node + queue의 역할을 겸하기에 이번에는 따로 분리 해주었다. 이번 작업에서는 queue를 이용한 트리에서 마지막 삽입된 노드를 찾는 흐름과 마지막 삽입된 노드의 부모를 찾는 작업의 흐름, 삽입되어야 할 위치를 찾기 위한 흐름을 보기위해서 삽입과 삭제시마다 queue를 새로 생성해서 찾게 하였다. 만약 적은 움직임으로 찾게 하고 싶으면, 트리의 선형적인 구조를 담은 queue를 어딘가 보관하고, 삭제할 노드의 부모노드에 대한 정보를 알고 있어야 한다. 구조 // tree -> node typedef st..

지난번 해시테이블 포스팅도 그렇고 이번 트리도 그렇고 꽤나 양이 방대해서 그런지 시리즈로 포스팅을 하고 있다. 나도 몰랐고 처음 해보는 자료구조들이라서 그런지 예제도 이해하는데 오래 걸리고 이를 토대로 다시 정리하는 것도 생각보다 오래 걸린다. ㅜ.ㅜ 으쌰 으쌰해야겠다. tree의 표현 방법 트리를 만드는 방법은 배열 혹은 연결리스트로 만드는 방법이 있다. 배열로 표현하는 방법은 다음과 같다. 임의의 노드 A의 부모노드 인덱스 . : 해당 노드의 인덱스 i / 2; 임의의 노드 A의 왼쪽 자식노드 인덱스. : 해당 노드의 인덱스 i * 2; 임의의 노드 A의 오른쪽 자식노드 인덱스. : 해당 노드의 인덱스 ( i * 2 ) +1 배열로 트리를 만들게 되면 배열의 0번째 방은 사용하지 않는다. 그리고 배열..

포스팅 전 주저리 : 알바하고 있는 곳에 전임자가 매니저로 왔다... 가뜩이나 사람들 자꾸 나가서 짜증난데 내가 정말 싫어하는 부류인 예의도 싸가지도 없는 놈이 매니저로 오다니 ㅜ.ㅜ 빨리 그만두라는 신의 계시인 것인가 ... ? Tree 란 ? Tree란 조직도같이 하나의 루트(하나 밖에 없는 차상위)에서 하층구조들과 연결된 계층적 자료구조를 말한다. 대표적으로 인공지능 문제에서도 트리가 사용된다고 한다. Tree를 이루고 있는 것들 Node : 데이터를 담는 공간이다. Root Node : 최상위 노드로 부모없이 가장 높은 곳에 있는 노드를 말한다. Edge : 부모와 자식노드를 연결해주는 선 Childe Node : 부모가 있는 노드로 위에 3의 데이터를 가지고 있는 노드입장에서 1을 가진 노드와 ..