6. 자료구조 & 알고리즘/6-1. 자료구조

자료구조 - [ AVL 트리 ]

AVL 트리 AVL(Adelson-Velsky And Landis) 트리는 스스로 균형 잡는 이진 탐색 트리로 삽입과 삭제 시 트리의 균형도를 계산하여 불균형을 완화하는 트리이다. AVL 트리는 균형도만 존재한다. 균형도가 절댓값 2 이상이면 불균형 트리이다. 균형도를 계산한 후 트리의 회전 여부를 판단하여 불균형할 경우 LL, RR, LR, RL 회전을 한다. null 노드인 경우 높이는 -1, 노드가 존재할 경우 노드의 높이는 Max(좌측 자식 노드 높이, 우측 자식 노드 높이) +1 균형도 = 좌측 자식 노드 높이 - 우측 자식 노드 높이 균형도가 양수인 경우 좌측 서브 트리가 비대한 트리, 음수인 경우 우측 서브 트리가 비대한 트리 Leaf노드는 항상 높이와 균형도가 0이다. LL 불균형 트리 부..

자료구조 - [ 이진 탐색 트리 ]

이진 탐색 트리는 부모 노드 기준 작은 키는 좌측 자식 노드로, 큰 키는 우측 자식 노드로 유지하는 트리이다. 이러한 자료 구조는 데이터 탐색 시 노드를 이동하면서 재귀적으로 탐색 가짓수를 1/2로 줄여나가며 찾는다. 그러나 이진 탐색 트리는 키의 삽입 순서에 따라 트리의 균형이 달라지기 때문에 트리의 균형을 예측하기가 어렵다는 단점이 있다. 1. 이진 탐색 트리 삽입 부모 노드보다 작으면 좌측 자식 노드로, 부모 노드보다 크면 우측 자식 노드로 배치한다. 따라서 부모 노드 기준 좌측 끝에 있는 노드는 트리에서 가장 작은 키가, 부모 노드 기준 우측 끝에 있는 노드는 트리에서 가장 큰 키가 된다. 2. 이진 탐색 트리 삭제 노드를 삭제 시에도 이진 탐색 트리의 구조를 유지해야 하기 때문에 특정한 규칙에 ..

자료구조 - [ 이진 트리 순회 ( 깊이 우선 / 너비 우선 ) ]

1. 깊이 우선 탐색 1) 전위 순회 (pre-order) 부모 노드를 선 방문 후 좌측 서브 트리와 우측 서브 트리를 방문하는 방법 void visit(Node node) { System.out.println(node.data); } void preOrder(Node parent) { if (null == parent) { return; } visit(parent); preOrder(parent.left); preOrder(parent.right); } 2) 중위 순회 (in-order) 좌측 서브 트리를 방문하고 부모를 방문 후 우측 서브 트리를 방문하는 방법 void visit(Node node) { System.out.println(node.data); } void inOrder(Node pare..

자료구조 - [ 재귀 - 점화식 관점 / 분할 관점 / 백트래킹 관점 ]

재귀(Recursion)란 컴퓨터 과학에서 자신을 정의할 때 자기 자신을 재참조하는 방식을 뜻하며 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 1) 순환적 특성이 존재해야 한다. 2) 순환을 종료할 중단 조건이 있어야 한다. // ex 1) public void A(...) { if(중단 조건) { } A(...); } // ex 2) public void A() { if(중단 조건) { } B(); } public void B() { if(중단 조건) { } A(); } // 반복문 public static void evenNumber() { for (int i = 1; i 10) { return; } else if (i % 2 == 0) { System.out...

자료구조 - [ Queue ]

큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO) 구조로 저장되며, 일반적으론 작업 대기열로 많이 사용된다. 또한 Thread Pool에서 작업을 저장하는데 큐가 사용되며 순차적으로 먼저 들어온 작업을 처리하는 데 사용된다.. 또한 메시지와 관련한 서버 간의 통신을 위해 사용되는 메시지 큐, 그리고 시스템 버퍼에도 사용된다. 큐를 구현하는 방법으로는 크게 배열을 이용한 Circle Queue와 연결 리스트를 이용한 Queue가 있다. 1. Circle Queue (배열) front는 데이터를 꺼낼 때 어떤 데이터를 꺼내야 하는지 배열의 index를 저장하는 값으로, 데이터를 꺼낸 후 1씩 증가한다. but 배열의 크기를 넘어서는 값을 가지지는 않는다. * front의 변경 범위 0

자료구조 - [ Stack ]

스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 구조로 되어 있으며, 데이터를 넣는 것을 Push, 데이터를 꺼내는 것을 Pop이라고 한다. 마지막에 들어간 것이 먼저 나온다는 후입선출(LIFO - Last In First Out)의 특징을 가지고 있다. 1. 배열로 Stack 구현 top은 데이터를 꺼낼 때 어떤 데이터를 꺼내야 하는지 배열의 index를 저장하는 값이다. 데이터를 넣을 때 top은 위로 이동하고, 데이터를 꺼낼 때는 top이 아래로 이동하며, 최솟값으로 -1을 가지고 최댓값으로 배열의 마지막 index를 가진다. * top의 변경 범위 -1