코드 썸네일형 리스트형 [자료구조/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] 덱 (Deque) - 연결 자료구조 방식 구현 * 덱 (Deque) "큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서, 큐와 스택의 성질을 모두 가지고 있는 자료구조이다." 따라서, 덱의 insertFront(), deleteFront() 연산은 Front 를 top으로 생각했을 때 스택의 push(), pop() 연산과 같고,insertRear(), deleteRear() 연산은 rear를 스택의 top으로 생각했을 때 스택의 push(), pop() 연산과 같다.그리고 덱의 insertRear(), deleteFront() 연산은 일반 큐의 enQueue(), deQueue() 연산과 같다. DequeNode.java123456789101112131415161718package Deque; public class DequeNode {.. 더보기 [자료구조/java] 큐 (Queue) - 연결큐 연결 자료구조 방식 구현 * 큐 (Queue) "스택과 달리 한쪽 끝에서는 삽입 작업이, 반대쪽 끝에서는 삭제 작업이 이루어진다." 따라서, 삽입된 순서대로 삭제되는 선입선출(FIFO, First-In-First-Out)의 구조로 운영된다. 줄을 서있다가 순서대로 앞에서부터 입장하는 줄서기도 큐의 선입선출 구조의 예가 될 수 있다. 큐는 한쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행하도록 하고, 가장 먼저 큐에 들어온 첫번째 원소이며, 다른 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행하도록 제한하고, 큐에 가장 늦게 들어온 마지막 원소이다. 큐는 다음과 같이 다섯가지의 기능을 구현해야 한다. (1) 공백 큐 생성 (createQueue) - 초기 상태의 공백큐는 저장된 원소가 없으므로 front와 rear를 -.. 더보기 이전 1 2 3 다음
