ColdLee ColdLee

앞선 글에서, RED-BLACK Tree : Insertion(삽입)에 대해 살펴보았다. 다음으로 RED-BLACK Tree : Deletion(삭제)에 대해 살펴보려고 한다. 시작 전에, Youtube에 아주 좋은 강의가 있어서 추천하려고 한다. 글을 읽기 전에, 시청하면 이해가 훨씬 수월하다. 링크 : https://www.youtube.com/watch?v=6drLl777k-E - RED-BLACK Tree Deletion(삭제) 삭제를 하기 전에 RED-BLACK Tree의 특성부터 정리하면 특성 1. 노드는 RED 혹은 BLACK 중의 하나이다. 2. Root 노드는 BLACK이다. 3. 모든 Leaf Node(NIL)은 BLACK이다. 4. RED 노드의 자식 노드 양쪽은 언제나 모두 BLAC..

앞선 글에서, RED-BLACK Tree의 개념에 대해 살펴보았다. 지금 부터는 RED-BLACK Tree의 동작에 대해서 살펴보려고 한다. 시작 전에, Youtube에 아주 좋은 강의가 있어서 추천하려고 한다. 글을 읽기 전에, 시청하고 오시면 이해가 훨씬 수월하다. 링크 : https://www.youtube.com/watch?v=2MdsebfJOyM - RED-BLACK Tree Insertion(삽입) 삽입을 하기 전에 RED-BLACK Tree의 특성부터 정리하면 특성 1. 노드는 RED 혹은 BLACK 중의 하나이다. 2. Root 노드는 BLACK이다. 3. 모든 Leaf Node(NIL)은 BLACK이다. 4. RED 노드의 자식 노드 양쪽은 언제나 모두 BLACK이다.(RED 노드는 연달..

1. 균형 이진 탐색 트리 균형 이진 탐색 트리란 노드의 삽입과 삭제가 일어나는 경우에 자동으로 각 노드에서의 높이를 균형있게 유지시키는 것. 단순히 이진 탐색 트리에 값이 오름차순 혹은 내림차순으로 삽입되는 경우 한쪽으로 치우치는 트리가 나온다. 시간 복잡도 : O(logN) --> O(N)이 되면서 문제가 발생한다. 균형 이진 탐색 트리는 위와 같은 문제점을 해결하여 최악의 경우에도 시간 복잡도 O(logN)을 유지 되도록 해주는 것. 종류로는 AVL-Tree, Red-Black-Tree와 같은 트리가 있다. 2. Red-Black Tree란? 레드 블랙 트리는 균형 이진 탐색 트리의 하나로써 각 노드를 RED, BLACK 2가지 색깔로 구분지어 트리의 균형을 맞춘다. Root에서 Leaf Node까..