반응형 Computer Science (CS)14 [Computer Science] 레드블랙트리(Red-Black Tree) AVL트리 -불균형 상태 일반적인 이진검색트리는 트리구조가 한쪽으로 치우쳐지는 경우가 있다. 이진검색트리의 검색성능은 높이에 의해 결정된다 → 한 쪽으로 치우치지않고 양쪽 균형을 맞추자! 하나의 노드를 기준으로 양쪽 서브트리의 높이 차이가 2 이상인 경우 balance factor : bf ( 왼쪽서브트리높이 - 오른쪽 서브트리의 높이) 가 절댓값 2 이사이면 불균형 불균형 상태가 되면 리밸런싱 작업을 수행한다. ( 회전을 통해 ) 여기에 15를 삽입해보자 →→현재 14의 높이는 2 , NIL의 높이는 0이므로 불균형 상태가 되었다. -회전 회전의 종류에는 1번만 회전하는 LL, RR 2번 회전시키는 LR,RL이 존재한다. 1. LL회전 -LL일때는 트리를 오른쪽으로 회전시켜주면 된다. 2. RR회전 R.. 2021. 10. 14. [Computer Science] 큐(Queue), 덱(Deck) 큐(Queue) 선입선출 (FIFO - First In First Out) Rear : 가장 뒤 ( 데이터가 들어오는 위치) Front : 가장 앞 ( 데이터가 나가는 위치) ex) 버스를 기다리는 줄, 은행에서 업무를 보기위해 기다리는 줄 등등 Enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부 Dequeue : 큐 맨 앞쪽의 요소를 삭제, 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제 Peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인 front : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호 rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호 선형큐 1차원 배열을 이용 인덱스를 값으.. 2021. 9. 13. [Computer Science] 이진트리 (Binary Tree) 이진 트리 모든 노드들이 2개의 서브트리를 갖는 형태의 트리 각 노드가 자식 노드를 최대 2가 가질 수 있음 왼쪽 자식, 오른쪽 자식 i 레벨에서 노드의 최대 개수는 2^i 개 (레벨의 노드 개수) 높이가 h인 이진트리가 가질 수 있는 노드의 최소 개수는 h+1 개 이며 최대는 2^(h+1)-1 개임 (전체 노드 개수) 포화 이진 트리 (Full Binary Tree) 모든 레벨의 노드가 포화상태인 이진 트리 높이가 h일때 2^(h+1)-1 개의 노드를 가짐 루트를 1번으로 해서 2^(h+1)-1 까지 정해진 노드 번호를 가짐 완전 이진 트리(Complete Binary Tree) 높이가 h 이고 노드수가 n일때, 포화 이진 트리의 노드 번호 1번 부터 n번까지 빈자리가 없는 이진 트리 순서대로 잘 정렬.. 2021. 6. 28. [Computer Science] 트리 (Tree) 트리의 정의 비선형 구조 원소들간에 1:n 의 관계를 가지는 자료구조 원소들간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위원소로 내려가면서 확장되는 나무모양의 구조 한개 이상의 노드로 이루어진 유한집합을 말하며 다음 조건을 만족함 노드중 최상위 노드를 루트(root)라고 한다 나머지 노드들은 n(≥0)개의 분리 집합 T1~TN 으로 분리될 수 있다. 사이클이 존재할 수 없다. (부모로 가는 간선은 한개며 다른 부모 노드는 하나임) 아래와 같이 표현이 가능 class Node { public String name; public Node[] children; } 이들 T1~TN은 각각 하나의 트리가 되며(재귀적 의미) 루트의 부 트리(subtree)라고 한다 트리에 나오는 용어 노드 - 트리의 원.. 2021. 6. 28. [Computer Science] 스택 (Stack) 스택(Stack) : LIFO구조, 마지막에 저장된 것을 제일 먼저 꺼내게 된다. 한 쪽 끝에서만 자료(데이터)를 넣고 뺄 수 있는 형식의 자료 구조 수식계산, 수식괄호검사, undo/redo, 뒤로/앞으로(웹브라우져) 스택(Stack)의 동작 삽입 - Push 스택에 새로운 데이터를 삽입하는 작업을 push라고 한다. 이는 top 값을 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다. 삭제 - Pop 스택에서 데이터를 제거하는 작업을 pop이라고 하며 이는 top이 가리키고 있는 자료를 삭제한 후 top 값을 하나 감소 시키도록 구현한다. 읽기 - Peek 스택에서 top이 가리키는 데이터를 읽는 작업을 peek이라고 하며 top 값의 변화는 없다. 2021. 6. 28. [Computer Science] 이중연결리스트 doubly linked list의 핵심은 노드와 노드가 서로 연결되어 있다는 점이다. 장점 '이중 연결 리스트'의 큰 장점은 양방향으로 연결되어 있기 때문에, 노드를 탐색하는 방향이 양쪽으로 가능하다는 것이다. 단일연결리스트의 경우는 맨끝의 데이터를 가져올때, 순차적으로 처음노드(head)부터 탐색을 해야한다. 단점 이전 노드를 지정하기 위한 변수를 하나 더 사용해야 한다. 구현이 '단일연결리스트'에 비해 복잡하다. public class DoublyLinkedList{ private Node head; private Node tail; private int size; public DoublyLinkedList(){ size = 0; } private class Node{ private Node nex.. 2021. 6. 28. 이전 1 2 3 다음 반응형
