red black tree
-
알고리즘 ch6 (2) Red-black tree학교 수업/알고리즘 2020. 6. 14. 20:48
Binary Search Tree- Binary Tree + Binary invariant(왼쪽 subtree는 더 작은 값 , 오른쪽 subtree는 더 큰 값)- 각각의 노드들의 key는 unique하며, 완쪽자식의 key는 부모보다 작으며 오른쪽 자식의 key는 부모보다 큰 값이다.- complexity 평균 최악 Insert O(logn) O(n) Remove O(logn) O(n) Search O(logn) O(n) 사슬모양처럼 긴 모양을 경우 최악의 경우고, balanced 모양일 경우 평균의 경우다. - 중회순회(inorder traversal) 시에 오름차순으로 정렬된 key값을 얻을수 있다. Red Black Tree- Binary search Tree 이면서 Balanced Tree이다..