Red-black Tree(with Java code)::자료구조
BST(Binary Search Tree)에서 높이를 log n으로 지향해 조금 더 균형 잡힌 트리로 만드는 기법입니다. - BST 조건을 만족하는 트리 구조 - 시간복잡도 O(log n) 1. Red-black Tree의 활용 자바 Collection에서 ArrayList의 내부적인 알고리즘이 RBT로 이루어져 있습니다. Map에서 HashMap의 Separate Chaining(충돌 처리 기법 중 하나, LinkedList로 Hash 충돌을 해결하는 방법)에서 사용됩니다. (Hash 충돌 기법에 대해서 더 알아보기 -> https://junboom.tistory.com/27) 2. Red-black Tree의 조건 - 모든 root 노드와 leaf 노드는 black의 색을 가집니다. - red의 색을..
2020.06.27