[알고리즘] Tree 5 - B tree

- 한 노드가  N개의 데이터와  N+1개의 자식 노드를 가질 수 있다.
- 노드 내의 데이터는 반드시 정렬된 상태여야 한다.
- Root노드는 적어도 2개 이상의 자식을 가져야 한다.
- Root노드를 제외한 모든 노드는 적어도 N/2의 올림 수 만큼의 자식을 가지고 있어야 한다.
- Leaf 노드는 모두 같은 레벨에 존재한다.
- 입력 자료는 중복되지 않는다.

자료의 입력

자료의 삭제

[알고리즘] Tree 4 - AVL tree

- 이진 트리이다.
- 각각의 노드마다 왼쪽과 오른쪽 sub-tree의 높이 차이에 대한 정보를 가지며 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다.
- O(lon n) 의 시간 복잡도로 검색, 삽입, 삭제를 할 수 있다.
- 삽입, 삭제 시 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 레드-블랙 트리 만큼 효율이 좋지 않아 자주 쓰이지 않는다.
- 노드가 삽입, 삭제 될 때 회전(rotation)을 통해 트리를 재구성 한다.

[회전]

균형이 맞지 않은 경우 (양쪽 서브트리의 높이 차이가 2이상 나는 경우)
아래와 같이 네가지 회전 방법을 통해 균형을 맞춰 준다.

LL

조건

왼쪽 서브트리의 높이가 오른쪽 서브트리 높이보다 2이상 크고
왼쪽 서브트리의 왼쪽 서브트리가 오른쪽 서브트리의 높이보다 큰 경우 
- left - left 로 길어짐으로 LL이라 명명한다.
- 오른쪽으로 돌려준다.

- 균형이 틀어진 노드를 NodeA라 하고 왼쪽 서브트리 쪽 첫번째 노드를 NodeB라 할 경우

NodeA.left = NodeB.right   NodeB.right = NodeA

RR

조건
오른쪽 서브트리의 높이가 왼쪽 서브트리 높이보다 2이상 크고
오른쪽 서브트리의 오른쪽 서브트리가 왼쪽 서브트리의 높이보다 큰 경우 
- right - right 로 길어짐으로 RR이라 명명한다.
- 왼쪽으로 돌려준다.

- 균형이 틀어진 노드를 NodeA라 하고 왼쪽 서브트리 쪽 첫번째 노드를 NodeB라 할 경우

NodeA.right = NodeB.left   NodeB.left = NodeA

LR

조건
왼쪽 서브트리의 높이가 오른쪽 서브트리 높이보다 2이상 크고
왼쪽 서브트리의 오른쪽 서브트리가 왼쪽 서브트리의 높이보다 큰 경우 
- left - right 로 길어짐으로 LR이라 명명한다.
- 서브트리를 왼쪽으로 돌려주고 다시 전체를 오른쪽으로 돌린다.

- 균형이 틀어진 노드를 NodeA라 하고 왼쪽 서브트리 쪽 첫번째 노드를 NodeB라 할 경우

RR(NodeB)   NodeB.right = NodeA

RL

조건
오른쪽 서브트리의 높이가 왼쪽 서브트리 높이보다 2이상 크고
오른쪽 서브트리의 왼쪽 서브트리가 오른쪽 서브트리의 높이보다 큰 경우 
- right - left 로 길어짐으로 RL 이라 명명한다.
- 서브트리를 오른쪽으로 돌려주고 다시 전체를 왼쪽으로 돌린다.

- 균형이 틀어진 노드를 NodeA라 하고 왼쪽 서브트리 쪽 첫번째 노드를 NodeB라 할 경우

LL(NodeB)   NodeB.left = NodeA

[삽입]

- BST와 같은 방식으로 삽입 후 균형이 맞지 않으면 회전으로 맞추어 준다.

[삭제]

- 삭제되는 노드가 leaf 노드인 경우 삭제만 하면 된다.
- 삭제되는 노드가 leaf 노드가 아닌 경우
  왼쪽 서브트리의 가장 큰 값 혹은 오른쪽 서브트리의 가장 작은 값으로 대체한다.
  leaf 노드가 될 때까지 반복하다 leaf 노드가 되면 삭제한다.
- 삭제 후에 균형이 맞지 않으면 회전으로 맞추어 준다.

[소스]

[알고리즘] Tree 3 - Binary Serch Tree

- 각 노드에 값이 있으며 키값은 모두 달라야 한다. 값들은 순서가 있다.
- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 가진 노드로 구성된다.
- 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 가진 노드로 구성된다.
- 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
- 중복된 노드가 없어야 한다.

노드 추가


노드 검색

노드 삭제
1. 자식 노드가 없으면 그냥 삭제한다.
2. 자식 노드가 하나면 자식 노드를 해당 노드 자리에 대체하고 삭제한다.
3. 자식 노드가 두개면 왼쪽 서브 트리의 가장 오른쪽 값이나, 오른쪽 서브 트리의 가장 왼쪽 값으로 대체하고 삭제한다.

노드 삭제 3번째 경우

최악의 경우

구현

[알고리즘] Tree 2 - 트리의 종류

1. 이진트리
 - 부모 노드 밑에 자식 노드가 최대 2개 올 수 있다.

2. B트리
 - 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 크다.
 - 데이터베이스와 파일시스템에 널리 사용된다.

[알고리즘] Tree 1 - 그래프

그래프

그래프는 꼭지점과 그 꼭지점을 잇는 변으로 이루어진다.
(이 때 꼭지점의 위치와 변의 길이는 상관하지 않는다.)

트리

 - 그래프의 일종
 - 여러 노드가 한 노드를 가리킬 수 없다.
 - 회로(Cycle)가 없다.
 - 서로 다른 두 노드를 잇는 길이 하나뿐이다.

[이클립스] 디버깅

브레이크 포인트 걸기

• 해당 소스 줄의 앞을 더블 클릭
• 해당 줄에 커서를 놓은 뒤 Ctrl + Shift + B
• 해당 줄에 커서를 놓은 뒤 메뉴에서 Run > Toggle Break 선택

디버깅 진행

F5 : 진행 시 메서드 호출이 있는 경우 메서드 안으로 들어간다. (Step Into)

F6: 메서드 호출이 안으로 들어가지 않고 다음 라인으로 이동한다. (Step Over)

F7: 현재 메서드에서 더이상 차례로 진행하지 않고 리턴한다. (Step Return)

F8: 다음 브레이크 포인트로 이동한다. (Resume)

[알고리즘] Quick Sort (퀵 정렬)

1. 배열 안에서 pivot이 되는 값을 정한다.

2. pivot값보다 작은 값은 왼쪽, pivot값보다 같거나 큰 값은 오른쪽으로 나누어준다. 

3. 나누어진 배열을 가지고 다시 1-2를 실행한다. 이는 나누어진 배열에 요소가 하나 남을 때까지 반복한다.

시간복잡도: O(nlogn)

장점:
- O(nlogn)의 복잡도를 가지는 다른 정렬 알고리즘보다 더 빠르게 수행된다.

단점
- 구현 방식이 효율에 크게 영향을 미친다.
- 이미 정렬된 데이터에 대해서 많은 시간이 걸린다.

코드

[알고리즘] Merge sort (병합정렬)

원소 개수가 1이 될 때까지 분할 한 뒤 분할한 역순으로 순서에 맞추어 병합 합니다.

분할

병합

while(true)

  정렬된 두배열을 하나의 배열의 끝에 다다를 때까지 순서대로 결과 배열에 넣는다.

이후 남은 배열을 결과 배열에 넣는다.

시간복잡도: O(nlogn)

장점

- 평균적으로나 최악의 경우에나 O(nlogn)의 복잡도를 갖는다.

- 연결 리스트의 정렬에 최적의 선택이 될 수 있다.

단점

- 추가 공간이 필요하다. 

코드

[알고리즘] Queue

처음 들어간 데이터가 가장 먼저 나오는 (FIFO: First In First Out) 자료구조

데이터 입력

데이터 출력

Queue 멤버변수 선언 및 초기화

데이터 넣기 & 데이터 빼내오기

가장 앞의 데이터 보기 & 비어 있는지 & 사이즈 & 내용출력

테스트 할 수 있는 메인

[알고리즘] Stack (LinkedList로 구현)

Double LinkedList 로 구현

멤버변수 선언 및 초기화

메소드들 구현

[알고리즘] Stack

마지막에 들어가는 데이터가 가장 먼저 나오는(LIFO: Last In First Out) 자료구조

데이터 입력

데이터 출력

Stack 클래스

main

Stack 클래스의 내용을 출력(Stack클래스 안에 선언함)

[관련 페이지]
LinkedList로 구현

[알고리즘] LinkedList _Double Linked List 구현

main

멤버변수 선언 및 생성자

노드 추가

인덱스에 해당하는 노드 삭제