트리
•
노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.
•
트리는 계층적 관계를 표현한다.
1.
트리는 하나의 루트 노드를 가진다.
2.
루트 노드는 0개 이상의 자식 노드를 갖는다.
3.
자식 노드 또한 0개 이상의 자식 노드를 갖는다.
4.
노드들과 노드들을 연결하는 간선들로 구성되어 있다.
•
루트 노드: 부모가 없는 노드
•
단말 노드: 자식이 없는 노드
•
내부 노드: 자식이 있는 노드
•
노드의 깊이: 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
•
노드의 레벨: 트리의 특정 깊이를 가지는 노드의 집합
•
노드의 차수: 자식 노드의 개수
•
트리의 차수: 트리의 최대 차수
힙
•
최대값 혹은 최소값을 빠르게 찾기 위한 완전이진트리
◦
이진트리
▪
이진트리는 컴퓨터 응용에서 가장 많이 활용되는 아주 중요한 트리 구조
▪
각 노드가 최대 두 개의 자식을 갖는 트리 구조
◦
완전 이진트리
▪
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 구조
▪
마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져 있어야 함
•
최소 힙이면 부모가 자식보다 작아야하고, 최대 힙이면 부모가 자식보다 커야한다.
•
값을 추가할 때는 마지막 레벨에 추가한 후(추가할 시 왼쪽부터 오른쪽 순서로 노드가 채워져있는지 확인 하면서 추가해야함) 부모노드와 비교하면서 자리 배치를 한다. logN
•
값 삭제할 때(값을 끄집어 낼 때)는 루트 노드와 마지막 노드를 바꾸고 루트 노드를 삭제한 후 비교하면서 자리 배치 logN
◦
자리 배치 break 할 경우는 최대힙에서는 자식노드들이 해당 노드보다 작을때 (
◦
해당노드의 자식들이 없을때 (while(leftNode≤size))
•
부모 노드 번호 = 자식 노드 인덱스 번호
•
왼쪽 자식 노드 번호 = 부모 노드 * 2
•
오른쪽 자식 노드 번호 = 부모 노드 *2 + 1
이진 탐색 트리
•
왼쪽 자식은 부모보다 작고, 오른쪽 자식릉 부모보다 큰 이진 트리
•
검색, 삭제, 삽입이 모두 높이인 (logN ~ N)이 된다.
•
N이 걸리는 것처럼 트리가 편향되지 않기 위해서 자가 균형 트리를 사용합니다.
자가 균형 트리
•
편향되지 않게 삽입, 삭제를 개선한 이진 탐색 트리
•
AVL, RedBlack
힙과 이진 탐색 트리의 공통점과 차이점
•
공통점: 힙과 이진 탐색 트리는 모두 이진 트리임
•
차이점:
◦
힙은 최대힙 경우에 각 노드의 값이 자식 노드보다 크거나 같음
◦
이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그다음 오른쪽 자식 노드 깂 가장 큼
•
이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨
해시
•
Hash: 방대한 데이터를 고정된 길이의 데이터로 변환하는 것
•
Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조
•
Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
•
해시에 매핑하여 데이터를 저장하는 자료 구조
•
해시값들로 바꿔주는것들을 해시 함수
•
버킷 대표 값을 해시
•
해시 함수에 들어가는 값을 키
k(키) → 해시 함수 h(k) → 해시 주소
•
key는 해시 함수를 통해 해시로 변경된 다음에 value와 매핑되어서 bucket에 저장되게 됩니다.
•
시간복잡도는 삽입, 삭제, 조회 모두 O(1)의 시간복잡도를 갖습니다.
해시 장점
•
데이터 저장/읽기 속도가 빠르다
•
해시는 키에 대한 데이터가 있는지 중복 확인이 쉽다
해시 단점
•
일반적으로 저장 공간이 좀 더 많이 필요하다
•
여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다
해시 충돌 회피 방법
•
Open Addressing: 다른 해시값에 저장
•
Chaining: 해쉬 테이블이 원소 하나를 담는게 아니라, Linked List를 담음
자바 Hash code
•
실행 중에 객체의 유일한 integer 값
•
객체 인스턴스의 주소 값을 비교하는 것은 동일성 비교(==)
•
객체 내부의 값을 비교하는 것은 동등성 비교(equals)
•
객체 해시코드란 객체를 식별하는 하나의 정수값을 말한다(이전에 자바로 구현했을 때 key값을 해시함수에 넣어 추출한 index라고 생각하면 될듯)
•
hashCode(): 메서드를 실행해서 리턴된 해시코드 ㄱ밧이 같은지를 본다. 해시 코드 값이 다르면 다른 객체로 판단하고 같으면
•
equals(): 메서드로 다시 비교한다. 이 두개가 모두 맞아야 동등 객체로 판단한다. 즉 해시코드값이 다른 엔트리는 동치성 비교를 시도조차 안한다.
equals() 오버라이딩 해주어야 하는 이유
•
참조하는 값이 같은지 확인하는 메서드이므로
•
개발자가 새로운 클래스 생성 후 equals로 동등성 체크를 해줄때에는 재정의해서 값이 같으면 논리적으로 동등하다고 파악하게 해야한다.
hashCode() 오버라이딩 해주어야 하는 이유
•
hash를 사용하는 collection는 value를 저장하기 위한 index를 구할 때 hashCode를 사용한다
•
hashCode는 메모리 주소 값을 반환하기 때문에 재정의 해주어야 한다.
