장영

📌레드블랙 트리의 다섯가지 속성 1.모든 노드는 red 혹은 black 2.루트 노드는 black 3.모든 nil노드는 black 4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다. 5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외) 📌rotatiom/recolor Rotation 을 통해 이진 탐색트리의 특성을 보전하면서 트리의 구조를 수정해 나갈 수 있고, 각각의 경우에 알맞게 Recolor 해주어 레드-블랙 트리의 특성을 만족시키도록 트리를 구성할 수 있다. RB tree 의 삭제 과정과, 삭제 후에 delete_fix_up 과정을 거치면서 RB tree의 특성을 만족시키도록 수정하는 과정들을 확인하려고 한다...

📌레드블랙 트리의 다섯가지 속성 1.모든 노드는 red 혹은 black 2.루트 노드는 black 3.모든 nil노드는 black 4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다. 5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외) 📌삽입 레드-블랙 트리에서 새로운 노드를 삽입할때 ,새로운 노드는 항상 red 만약 트리가 레드블랙 트리의 특성을 위반한다면, 두가지 방법을 통해 트리의 구조를 조정한다. recolor rotation 📌삽입 과정 키 값이 20인 노드를 삽입하는 과정을 생각해보자. target Node를 20으로 설정하고 시작. key = 20인 노드가 들어갈 위치 탐색 key = 20 < 28 이고,..

Red-black 트리의 삭제 방식 📌삽입 overview 삭제전 RB트리의 속성을 만족한 상태 삭제 방식은 일반적인 BST와 동일 삭제 후 RB트리 속성 위반 여부 확인 RB트리 속성을 위반했다면 재조정 RB트리 속성을 다시 만족 💡속성 위반 여부 확인 RB트리에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요! 💡삭제되는 색이란? 삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 색=삭제되는 노드의 색(여기선 유요한값을 가지는 자녀를 의미 닐노드는 포함 x) 25 삭제 -> red 삭제 80 삭제 -> black 삭제 40 삭제 -> black 삭제 📌삭제하려는 노드의 자녀가 둘이라면 삭제되는 색 = 삭제되는 노드의 successor의 색 👉🏻20 삭제 -> succ..

Red-Black 트리의 삽입 방식 📌삽입 overview 삽입 전 RB 트리 속성을 만족한 상태 삽입 방식은 일반적인 BST와 동일 삽입 후 RB트리 위반 여부 확인 RB트리 속성을 위반했다면 재조정 RB트리 속성을 다시 만족 💡삽입 노드의 색 삽입하는 노드는 항상 RED이다. 삽입 예제 📌레드블랙 트리의 다섯가지 속성 1.모든 노드는 red 혹은 black 2.루트 노드는 black 3.모든 nil노드는 black 4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다. 5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외) 📌insert(50) 노드를 삽입 할 때 두 nil 노드의 색은 black으로 고정한다. 그러면 ..

레드 블랙 트리를 소개할 것이지만 먼저 이진검색 트리를 알아보도록 하겠습니다. 이진검색트리 단순히 정렬되거나 정렬된 이진트리 각 노드는 두개의 서브 트리를 가질 수 있습니다. 특정 노드의 왼쪽에 있는 항목은 더 작고 오른쪽에 있는 노드가 더 큽니다. 이것은 매우 간단하지만 다음과 같은 경우에는 한쪽으로 편향되었을때 삽입,삭제,검색 시 시간복잡도가 O(n)입니다. 이 말은 최악의 경우 노드를 하나 찾으려면 모든 노드를 방문해야하는 합니다. 이 단점을 개선하기 위해 편향된 구조가 되지 않도록 하는 레드블랙 트리가 등장. 레드-블랙 트리(Red-Black Tree) 📌레드블랙 트리 개념 이진탐색트리의 한종류 스스로 균형을 잡는 트리 BST의 단점을 개선 모든 노드는 red 혹은 black 💡nil 노드란? 존..