자료구조(DataStructure)
-
B Tree (B 트리)자료구조(DataStructure) 2013. 6. 20. 18:30
특징 및 개념 정렬된 데이터 보존. 로그시간내에 검색, 순차접근, 삽입, 삭제가 가능. 노드가 가득차 있지 않기 때문에 일정부분의 공간이 낭비됨. 모든 리프노드가 같은 깊이를 가지게 됨. B트리의 노드들은 여러개의 키를 가지고 있고, 이 키를 기준으로 하위트리들을 나누게 됨. 자식노드의 개수는 키개수+1 이 됨. 정의 각 노드의 키값은 하위트리들을 나누는 값이 되어야 함. 차수가 m인 B 트리는 다음 속성들을 만족시켜야 함. 1. 모든 노드는 최대 m 개의 자식들을 가져야한다. 2. 리프노드가 아닌 모든 노드(루트노드 제외)는 최소한 m/2개의 자식을 가져야 한다. 3. 루트 노드는 최소한 2개의 자식을 가져야 한다. 4. k개의 자식을 가지고 있는 리프노드가 아닌 노드는 k-1개의 키를 가진다. 5. ..
-
Linked List (링크드 리스트, 연결 리스트)자료구조(DataStructure) 2013. 6. 19. 17:53
개념 및 용어 링크드 리스트의 개별 데이터들을 원소(element) 또는 노드(node)라고 함. 각 노드는 다음 노드의 주소를 가지고 있는데 이 걸 다음링크(next link) 또는 다음 포인터(next pointer)라고 함. 그외 data, information, value, cargo, payload등의 필드를 가지고 있음. 리스트의 첫번째 노드를 헤드(head)라고 함. 종류 싱글 링크드 리스트(Singly linked list) 노드가 데이터 필드와 다음 노드를 가르키는 필드로 구성됨. 더블 링크드 리스트(Doubly linked list) 각 노드들이 양옆의 노드에 대한 링크를 가지고 있음. 다중 링크드 리스트(Multiply linked list) 각 노드들이 링크에 대한 필드를 2개 이상..
-
Binary Search Tree (이진 탐색 트리)자료구조(DataStructure) 2013. 6. 17. 13:52
이진 탐색 트리란? 노드기반 이진 트리 데이터 구조. 속성 * 노드의 왼쪽 하위트리는 노드의 키보다 작은 키를 가진 노드들만 가지고 있음. * 노드의 오른쪽 하위트리는 노드의 키보다 큰 키를 가진 노드들만 가지고 있음. * 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 함. * 중복된 노드가 없어야 함. 검색방법. 1. root 노드부터 시작 2. 트리가 null이면 값이 없음. 3. root와 키가 같으면 찾기 성공 4. 키가 루트보다 작으면 왼쪽 하위트리검색, 키가 루트보다 크면 오른쪽 하위트리 검색 5. 하위트리가 null이 될때까지 이 과정 반복. 검색 시간복잡도 평균 : O(log n) 나쁜경우 : O(n) 삽입 삽입은 검색부터 시작. 트리를 검색한 후 키와 맞는 노드가 없으면 마지막 노드에..
-
Tree Structure (트리구조)자료구조(DataStructure) 2013. 6. 13. 10:16
정의 자료의 상속구조를 그래프 형태로 보여주는 방법. 나무(tree)형태로 보여지기 때문에 트리 구조라고 함. 실제 나무를 뒤집어 놓은 형태로 최상단이 루트(root, 뿌리)가 되고 하단이 리프(leaves, 잎)가 됨. 용어 루트노드(root node) 상위노드가 없는 노드. 루트 노드는 시작하는 노드이지만, 시작하는 노드가 루트노드는 아님. 무한 트리 구조에서는 루트노드가 있을수도 없을수도 있음. 브랜치(branches) 원소들을 연결하는 선 노드(nodes) 각 원소들 리프 노드(leaf nodes) 자식이 없는 노드 부모노드(parent node) 상속구조에서 한단계 상위에 있는 노드. 같은 브랜치상에 있음. 형제노드(Sibling, Brother, Sister) 같은 부모노드를 가지는 노드들 삼..