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. [Data Structure] HashMap 보다 Tree 를 써야 하는 곳에 대해 알아보면서 알게 된 내용들 [Data Structure] HashMap 보다 Tree 를 써야 하는 곳에 대해 알아보면서 알게 된 내용들 Wikipediahttps://brackece.wordpress.com/2012/09/18/hash-table-vs-binary-search-tree/ - F B GA D I C E H Preorder(전위순회) or Depth-First Search (DFS, 깊이 우선순회) 로직 : 노드 방문 -> 왼쪽 서브 트리 Preorder -> 오른쪽 서브 트리 Preorder ex) F -> B -> A -> D -> C -> E -> G -> I -> H Inorder(중위 순회) or Symmetric Search 로직 : 왼쪽 서브 트리 Inorder -> 노드 방문 -> 오른쪽 서브 트리 I.. 2019. 1. 12. [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 다음
