Computer Science/Data Structure
2022. 1. 21.
[Data Structure] Red Black Tree
Red Black Tree RBT는 이진 탐색 트리를 기반으로 하는 트리 형식의 자료구조이다. 시간복잡도 Search : O(log n) Insert : O(log n) Delete : O(log n) 동일한 노드의 개수일 때 depth를 최소화하여 시간 복잡도를 줄인다. 동일한 노드의 개수일 때 depth가 최소가 되는 경우는 tree가 완전 이진 트리인 경우이다. 정의 Red-Black Tree는 다음의 성질을 만족하는 이진 탐색 트리이다. 각 노드는 Red 또는 Black이라는 색을 가진다. Root는 Black이다. 각 leaf는 Black이다. 어떤 노드가 red라면 두 개의 자식은 모두 black이다. 각 노드에 대해서 해당 노드를 루트로 보는 서브 트리가 있을 때, 서브트리의 루트에서 각 리..
![[Data Structure] Red Black Tree](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/ogoPG/btrrqZGXaBn/Qqtwt6EXpln0skHOh0Udz0/img.png)