리루

정의 트리는 노드(node)라는 항목들이 계층적으로 배치되어 구성된다. 계층의 가장 상위 노드를 루트(root)라고 한다. 루트의 바로 아래 노드들은 루트의 자식들(children)이고, 보통 이 노드들도 자식이 있다. 루트를 제외한 모든 노드들은 하나의 부모(parent)를 갖는데 부보는 바로 상위 노드이다. 부모가 가질 수 있는 자식 노드의 수는 트리의 형태에 따라 다른다. 트리에서 이 숫자를 분기계수(branching factor)라고 한다. 응용 1. 이진트리 자식을 두 개까지 가질 수 있는 노드들로 이루어진 트리이다. 2. 트리 평형 주어진 수의 노드들에 대해 트리를 가능한 짧게 유지하는 데 사용되는 방법이다. 트리의 높이가 전체 성능에 영향을 미치기 때문에 필요한 부분이다. 3. 사용자 인터페..

- 해시 테이블은 가장 효율적인 탐색 중 하나인 해싱을 제공한다.- 기본적으로 해시 테이블은 키(key)라는 특별한 인덱스로 자료에 접근하는 배열로 구성된다.- 해시 테이블의 주 개념은 모든 가능한 키들과 배열의 위치 사이에 해시 함수를 이용해서 매핑(mapping)을 만드는 것이다.- 해시 함수는 키를 전달 받아서 그 키의 해시 값(hash coding or hash value)을 리턴한다.- 키들의 형은 다양하지만 해시 값은 항상 정수이다. - 해시 값을 계산하는 것과 배열에서 특정 위치의 값을 얻는 것은 모두 상수 시간에 실행되므로 해싱의 매력은 상수 시간 탐색을 제공하는 점이다.- 해시 함수가 임의의 키에 대해 같은 해시값을 리턴하지 않는다면 이 때 생성되는 해시 테이블은 직접 참조된다라고 한다...

집합(Set)은 - 원소(Member)라는 구별되는 객체들이 연관되어 모인 것이다. - 서로 다른 연관된 원소들의 순서 없는 모임이다. 특징- 순서가 없다.- 원소들끼리 서로 다르다 응용1. 그래프 - 객체들 사이의 관계나 연결로 정의되는 문제(?)들을 모델링하는 데 전형적으로 사용되는 자료구조다. - 그래프를 표현하는 가장 일반적인 방법은 인접 리스트(adjacency list)를 사용하는 것이다. - 인접 리스트는 하나의 정점에 인접한 정점들을 갖는다. - 인접 리스트를 표현하는 한 방법은 인접한 정접들의 집합으로 표현하는 것이다. 2. 그래프 알고리즘 - 그래프로 모델링되는 문제들을 푸는 알고리즘이다. - 흔히 그래프 알고리즘은 정점들이나 에지들을 함께 모으는 데 집합을 사용한다. - 예를들어, 최..