목록zerebase/자료구조 (15)
Hyunebee
레드블랙 트리의 조건 1. root 노드와 leaf노드의 색은 black 2. red 색 노드의 자식은 black 3. 모든 leaf노드에서 root노드까지 가는 경로의 black 노드 수는 같음 조건을 만족하지 못할시 재배치해야함 여기서 NIL은 null Node라 생각하면됨 삽입 double red 발생 - (1) -부모 노드의 형제 노드가 red일때 이때는 색을 바꿔줌 -삽입한 노드의 부모와 부모의 형제 노드를 black으로 변경 -부모의 부모노드를 red로 변경 -부모의 부모노드가 root인지 double red인지에 따라 조정 double red 발생 - (2) -부모 노드의 형제 노드가 black이거나 없을때 이때는 위치를 바꿔줌 대상: 삽입한 노드, 부모 노드, 부모의 부모노드 -조정 노드들..
이진탐색트리 1. 각 노드는 키값을 하나씩 갖는다. 각 노드의 키값은 모두 달라야한다. 2. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두개의 자식을 갖는다. 3. 임의의 노드의 키값은 왼쪽 자식보다는 크고 오른쪽 자식보다는 작다(Node.left < key < Node.right) 4. 중복된 키를 허용하지 않음 5. 트리임으로 사이클을 허용하지 않는다. 특징 1.중위순회로 데이터를 뽑을시 데이터가 정렬된 상태를 유지한다. 2.이진 트리에 비해 탐색이 빠르다. (균형 O(logN), 불균형 상태O(N)) 이진 탐색트리의 삽입 1.Root 부터 비교시작 2.삽입할 키와 비교해서 작으면 왼쪽 크면 오른쪽 Leaf노드까지 오면 비교후 삽입 ex) for Node head;// root 노드드 Bina..
해시 테이블 원소를 키와 값으로 저장한다. 저장시 키를 해시함수에 넣어서 해시테이블에 저장하게 된다. 해싱 함수는 여러가지 방법에 따라 만들수있다. 대표적으로 Division Method, Multiplication Method가 있다. 이상적인 해시 함수는 입력원소가 해시 테이블에 고루 저장되는것이 좋다. Division Method h(x) = x mod m m: 해시테이블 사이즈이며 대개 소수로 작성된다. Multiplication Method h(x) = (xA mod 1) * m A : 0 < A < 1인 상수 m: 굳이 소수일 필요는 없고 보통 크기는 2^n으로 잡는다. ex) 크기가 9인 해시테이블에 5개의 원소를 저장 (입력 : 20 , 9 , 15, 24 ) (해시함수 h(x) = x m..
큐 먼저 집어 넣은 데이터가 먼저 나오는 (First In First Out)구조로 저장하는 형식 자바에서는 Queue를 인터페이스 형식으로 제공하고 있다. Collection을 상속받기 때문에 ArrayList LinkedList등을 통해 구현할 수 있다. 큐는 선형 자료구조이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다. -> 크기제한을 환형으로 극복가능 예제) 환형 큐 구현 위의 그림처럼 Front는 나가는 idx back은 들어오는 idx라고 생각하면 편하다. 여기서 back은 rear로 나타내고 있 다. 배열의 크기는 +1을 더해준다.
Stack 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 마지막으로 들어간 데이터가 처음에 나오는 데이터 구조이다. push로 밀어넣고 pop으로 꺼낸다. 이때 pop을 하면 Stack에 있는 데이터는 사라진다. 예제) 1. 괄호 찾기 2. 전위/후위/중위 표기법 일단 전위 후위 중위 표기법에 대해서 알아야 한다. (연산자 데이터 데이터) 중위 표기법 : 우리가 기존 사용하는 표기법 1+ 2 (데이터 연산자 데이터) 전위 표기법 : 연산자를 데이터 앞에 넣어줌 (데이터 데이터 연산자) 사직연산의 우선순위로 계산을 시작한다. 중위 -> 전위 A * (B+C)/D-E : (B+C) 괄호임으로 가장 먼저 연산자가 맨앞으로 A *+BC..
단방향 LinkedList 데이터를 링크로 연결해서 관리하는 자료구조 자료의 순서는 정해져 있지만, 메모리상의 연속성은 보장되지 않음 장점 1. 데이터의 공간을 미리 할당할 필요없음 -> 데이터의 추가/ 삭제가 용이하다. (메모리의 시점에서) 단점 1. 연결구조를 위한 별도의 데이터가 필요하다.(이전노드, 다음노드) 2. 연결 정보를 찾는 시간이 필요하다.(메모리 상의 연속성이 보장되지 않기 떄문에) 3. 데이터의 추가/ 삭제시 앞뒤 데이터의 연결이 필요하다. (코딩 관점) 구현 예제 양방향 LinkedList 구현 예제 두예제 전부 그림으로 생각하면 쉽다.
배열 배열의 특징 1. 데이터와 인덱스가 1:1로 대응 2. 데이터가 메모리상에 연속적으로 저장됨 배열의 장단점 1. 인덱스를 이용해서 빠르게 접근이 가능하다. 2. 최대길이가 정해져 있다. -> 데이터의 추가 또는 삭제가 번거롭다. 삭제와 삽입 두개의 배열을 이용해 합쳐주는 방식으로 구현했다. -> 데이터의 추가 또는 삭제가 번거롭다. // 배열에 데이터 삽입 public void insertData(int index, int data){ if(index < 0 || this.arr.length < index){ System.out.println("Index Error"); return; } int[] arrDup = this.arr.clone(); this.arr = new int[this.arr.l..