자료구조 썸네일형 리스트형 [자료구조/java] 힙 (Heap) - 배열 구현 * 힙 (Heap) "완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조" - 최대 힙 (Max Heap) 키값이 가장 큰 노드를 찾기 위한 힙 (부모노드의 키값 >= 자식노드의 키값)- 최소 힙 (Min Heap) 키값이 가장 작은 노드를 찾기 위한 힙 (부모노드의 키값 더보기 [자료구조/java] 이진 탐색 트리 BST (Binary Search Tree) - 연결 리스트 구현 * 이진 탐색 트리 (Binary Search Tree) "탐색을 위한 자료구조로 이진 트리를 사용하기 위해서 저장할 데이터의 크기에 따라 노드의 위치를 정의한 것"- 전화번호부에서 전화번호를 찾거나 - 서점에서 책을 찾거나 - 지도에서 목적지를 찾는것등과 같이 자료들 속에서 필요한 자료를 찾아내는 것이 탐색이다.탐색을 하기 위해서 찾을 자료를 식별할 수 있는 유일한 값이 필요한데 이것을 키(key)라고 한다.사람을 찾을 때 그 사람을 식별할 수 있는 주민등록번호나 학번을 사용하였다면 이것이 탐색키가 된다. 효율적인 탐색 작업을 위해 이진 탐색 트리를 다음과 같이 정의한다. (1) 모든 원소는 서로 다른 유일한 키를 갖는다. (2) 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다. (3) 오른.. 더보기 [자료구조/java] 이진 트리 (Binary Tree) 의 순회 (traversal) * 이진 트리 (Binary Tree) 의 순회 (traversal) "순회(traversal)" 이진 트리에 있는 모든 노드를 한번씩 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 것 - 리스트나 스택, 큐와 같은 선형 자료구조는 순회하는 방법이 한 가지였지만, 트리는 계층적인 구조를 가지고 있기 때문에 여러가지 순회 방법이 있을 수 있다. (1) 현재 노드를 방문하여 데이터를 읽는 작업 D (2) 현재 노드의 왼쪽 서브트리로 이동하는 작업 L (3) 현재 노드의 오른쪽 서브트리로 이동하는 작업 R - 서브트리를 순회하는 순서는 항상 왼쪽 서브트리를 먼저 방문하고, 그 후에 오른쪽 서브트리를 방문한다.- 노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나눌 수 있다. ★ 전위 순.. 더보기 [자료구조/java] 이진 트리 (Binary Tree) - 순차 자료구조 방식, 연결 자료구조 방식 * 이진 트리 (Binary Tree) 구현 - 순차 자료구조 방식 - 이진트리를 배열로 표현하는 방법은 높이가 h인 포화 이진 트리의 노드번호를 배열의 인덱스로 사용하여 1차원 배열로 표현 - 1차원 배열에서 인덱스 계산을 간단히 하기 위해서 인덱스 0번은 실제로 사용하지 않고 비워두고 항상 인덱스 1번에 루트를 저장 이진 트리를 표현한 1차원 배열에서의 인덱스 관계를 나타낸 표이다. * 이진 트리 (Binary Tree) 구현 - 연결 자료구조 방식 - 배열을 이용한 순차 자료구조 방식은 쉽게 만들 수 있고, 인덱스 규칙에 따라 노드를 찾는 것이 쉽다. - 하지만 메모리 사용에 있어서 완전 이진 트리의 경우 최적의 공간 사용이 되지만, 편향 이진 트리의 경우 많은 공간이 낭비된다. - 메모리 문제와 .. 더보기 [자료구조/java] 이진 트리 (Binary Tree) * 이진 트리 (Binary Tree) "노드의 차수를 2 이하로 정하여 트리의 노드구조를 일정하게 정의함으로써 연산을 단순화 시킨 트리" - 이진트리는 왼쪽 자식노드와 오른쪽 자식노드 2개만을 가질 수 있다. (공백 노드도 이진 트리의 노드로 취급)- n개의 노드를 가지는 이진 트리는 항상 (n-1)개의 간선을 가진다. - 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1)-1)개가 된다. * 이진 트리 (Binary Tree)의 분류 포화 이진 트리(Full Binary Tree)- 모든 레벨에 노드가 꽉 차서 포화 상태인 이진 트리를 의미- 높이가 h 일때 2^(h+1)-1 개의 최대 노드수를 갖는 이진트리 완전 이진 트리(Complete B.. 더보기 이전 1 2 3 4 다음
