Data Structres
-
[ Open Data Structures ] Red-Black Trees - 3DataStructure 2021. 1. 23. 16:53
2-4 Tree와 Red-Black Tree(이하 RBT)가 명백한 관계가 있음을 보였습니다. 추가로 Add/Remove Operation을 RBT에서도 효과적으로 수행할 수 있다는 사실도 확인했습니다. 이미, Binary Search Tree에서 새로운 Leaf node를 추가함으로써 Add operation을 구현할 수 있다는 점은 알고 있습니다. 따라서 2-4 Tree에서 보았던 5개의 Children node를 분할하는 Split method를 RBT에 적용하는 것이 핵심이 될 것입니다. 5개의 Children node를 가진 node는 RBT에서는 하나의 Black node를 가진 Red node와 red node하나, 총 두 개의 Red node를 Children node로 가지는 Black ..