AVL Tree, Red Black Tree AVL Tree, Red Black Tree -AVL 과 Red Black Tree 는 모두 Self balancing B-Tree 이며, Self balancing 을 최적화하여 유지하는 알고리즘이 적용된 Tree 라고 보면 된다.Red Black Tree 가 AVL 보다 성능이 좋아 Red Black Tree 가 잘 쓰인다. AVL Tree -가장 초기에 나온 balanced B-Tree. -각각의 노드마다 왼쪽과 오른쪽 sub-tree 의 높이차이에 대한 정보를 가지며, sub-tree 의 높이 차이가 1보다 크지 않은 성질을 가진다. -O(log n) 으로 검색, 삽입, 삭제를 할 수 있다. -삽입, 삭제를 할 때 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 Red Black B-Tre.. 2019. 1. 14. [DSA] Search & Sorting Algorithm Tutorial [DSA] Search & Sorting Algorithm Tutorial https://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm - Linear Search 는 O(n) 의 complexity 를 갖는다. - Binary Search 는 O(log n) 의 complexity 를 갖는다. Divide and Conquer 방식이 기본이다. Binary Search 가 작동하려면 sorting 이 되어 있어야 한다. Mid position 에 있는 녀석이 찾으려는 녀석인지 확인한다. 찾으려는 녀석이 그 녀석보다 작으면 아래쪽을 다시 binary search 하고, 크면 위쪽을 다시 binary search .. 2019. 1. 13. [Map] HashMap vs. TreeMap vs. LinkedHashMap [Map] HashMap vs. TreeMap vs. LinkedHashMap -HashMap Key 는 equals 와 hashCode 가 구현되어 있어야 한다. O(1) time complexity -TreeMap ( SortedMap ) Key 가 Red-black tree structure 를 사용하여 ordering 되어 있는 형태의 Map Key 가 Comparable 을 구현해야 한다. 그래야 tree 에서 비교를 할테니... ( 참고로 String 은 Comparable 하다 ) Key 가 정렬되어 있다는 의미는 keys() 나 entrySet() 을 가지고 왔을 때, Comparable.compare 에 의한 정렬결과 순으로 collection 이 구성된다는 것이다. Tree 를 사용했다.. 2019. 1. 11. 반응형 이전 1 다음
