줄기교실2017/1119 - Revision history

165.194.17.62 at 10:34, 19 November 2017

2017-11-19T10:34:04Z

← Older revision		Revision as of 10:34, 19 November 2017
Line 35:		Line 35:

	* c++에서 연산자 오버로딩이 돼있다면 std::sort로 정렬이 가능하다.		* c++에서 연산자 오버로딩이 돼있다면 std::sort로 정렬이 가능하다.

			* sorting의 stability

165.194.17.62 at 10:17, 19 November 2017

2017-11-19T10:17:18Z

← Older revision		Revision as of 10:17, 19 November 2017
Line 14:		Line 14:
	** 왼쪽에서부터 가득 차 있는 tree를 complete tree라고 한다.		** 왼쪽에서부터 가득 차 있는 tree를 complete tree라고 한다.
	** 모든 자식이 풀로 차 있으면 full tree라고 한다.		** 모든 자식이 풀로 차 있으면 full tree라고 한다.

			* Tree Search(traversal)
			** 1. depth-first
			** 세로로 먼저 스캔한 다음
			** pre-order : 나 보고 왼쪽 보고 오른쪽 보고
			** in-order : 왼쪽 보고 나 보고 오른쪽 보고
			** post-order: 왼쪽 보고 오른쪽 보고 나 보고
			** 2. breadth-first
			** 가로로 스캔하는 방식(level-order)
			** queue를 이용하면 출력이 용이하다.
			** queue에서 자신을 빼서 출력에 넣고 자식을 queue집어넣는다.

			* priority queue
			** 값이 가장 큰(작은) 순서대로 튀어나오는 것
			** heap으로 구현한다.
			** 연산 : insert, top, pop
			** insert : complete를 유지할 만한 자리에 넣고 부모와 비교한 다음 부모가 자신보다 크다면 둘의 값을 교체한다.
			** top : 비용이 1만큼 든다.
			** pop :

			* c++에서 연산자 오버로딩이 돼있다면 std::sort로 정렬이 가능하다.

165.194.17.62: {CREATE}

2017-11-19T09:25:34Z

{CREATE}

New page

* Tree
** 이진트리의 제일 상위 노드를 root(헤드)
** 이진트리의 제일 하위 노드를 leaf
** parent - child
** ancestor - descendant
** siblings : 위로 갔다가 아래로 가는 방향(형제)
** Tree는 한 개의 노드와 여러개의 subtree로 구성된다.
** tree의 가장 긴 level을 height로 한다.(정의에 따라 +-1)
** 최대로 가질 수 있는 자식의 개수를 degree라고 한다. k-nary tree
** cycle이 없는 그래프를 tree라고 한다.

* Binary Tree
** 왼쪽 자식과 오른쪽 자식을 따로 정의한다.
** 왼쪽에서부터 가득 차 있는 tree를 complete tree라고 한다.
** 모든 자식이 풀로 차 있으면 full tree라고 한다.