2JINISHAPPY 2JINISHAPPY

https://2jinishappy.tistory.com/318 Color를 이용해서 Self-Balancing을 구현하는 Red-Black Tree 자료구조와 알고리즘을 공부한 사람이라면 레드블랙트리에 대해 한번쯤은 들어봤을 것 이다 포인터가 중간보스라면 레드블랙트리가 최종보스라고 생각하는데 .. 3부작 정도로 나눠서 레드블랙 2jinishappy.tistory.com 이전 글에서 소개한 것 처럼 레드블랙트리는 BST의 탐색/삽입/삭제 시간을 로그 시간에 수행하기 위해 등장했다 삽입 및 삭제 연산은 red-black property를 해칠 수 있기 때문에 balance를 유지하기 위한 Rotation 연산이 필요하다 이 글에서는 탐색/삽입 연산에 대해 설명한다 Search Node in RBT 레드블랙..

자료구조와 알고리즘을 공부한 사람이라면 레드블랙트리에 대해 한번쯤은 들어봤을 것 이다 포인터가 중간보스라면 레드블랙트리가 최종보스라고 생각하는데 .. 3부작 정도로 나눠서 레드블랙트리를 정리하려고 한다 레드블랙트리가 무엇인지에 대해 알기 전에, 레드블랙트리가 어디에서 사용되는지에 대해 두 가지를 소개하자면 Java Collection API의 Map Interface 구현체인 HashMap의 Seperate Chaining 구현에서 사용한다. 👉 Key값의 Collision이 발생할 경우 같은 Hash값을 가지는 원소들을 Collection으로 관리하는데, 이 때 원소의 개수가 많아지면 Red-Black 트리를 이용해서 관리하여 연산 시간을 O(log)으로 관리한다 Linux의 기본 스케줄러인 CFS 스..