school of computing/Data structure (3) 썸네일형 리스트형 자료구조 | Ch03. Binary Search Tree 1. Binary Search Binary Search에서 값을 찾는 알고리즘은 아래와 같다. 1. 정렬된 값에서 중간값을 찾는다. 2. 찾고자 한 값이 중간값과 같으면 성공, 만약 값이 하나밖에 남지 않았을때 찾는 값과 중간값이 다르면 실패한 것이다. 3. 만약 찾는 값 중간값 이면, 중간값의 오른쪽 list로 가 위 과정을 반복한다. 2. Binary Search Tree 위 Binary Search를 Tree로 구현한 것이 Binary Search Tree이다. 정렬된 Binary Tree는 항상 Left < Root < Right를 만족해야한다. 전체 Tree로 보았을 때 한 root의 left SubTre.. 자료구조 | Ch02. Binary Tree 1. Binary Tree란? Binary Tree는 모든 node가 2개 이하의 child node를 가지고 있는 tree이다. (모든 node의 degree > General Tree를 Binary Tree로 옮기는 과정에서 모든 node는 포함된다. node의 상대적 level관계는 보존되지 않는다. ex) Level of E > Level of C ----> Level of E == Level of C parent-decendant 관계는 보존된다 ex) node H는 node D의 descendant ----> node H는 node D의 descendant 3. Coding in C 각각 노드는 structure로 만든다. node의 key의 데이터 타입은 상황에 따라 변경할 수 있고 한 no.. 자료구조 | Ch01. Trees 1. Tree란? Tree는 list, stack, queue와 달리 none-linear 구조 이다. Tree는 root와 leaf, interior nodes로 구성되어있다. Root node : parent node가 없는 node이다. Tree의 시작 node. Leaf node : child node가 없는 node이다. Interior node : root node나 leaf node가 아닌 node. Sibling node : 같은 parent node를 가진 node. Descendant node : 노드의 Child node의 Child를 한 node의 descendant라고 정의한다. Ancestor node : 노드의 Parent node의 parent를 한 node의 ancestor.. 이전 1 다음
