진 -> 민수

[jjinleee]

1. 이진힙과 이진 탐색트리의 차이점과 각 장단점은 무엇인가요?
2. 레드 블랙트리의 속성과 균형을 유지하는 방법인 무엇인가요?

[skyriv213]

이진 힙은 힙의 또 다른 표현입니다. 그리고 힙은 이진트리의 종류 중에 하나인 완전 이진트리를 바탕으로 구현된 자료구조 입니다.

그렇기에 힙과 이진 탐색트리의 차이점은 완전 이진 트리와 이진 탐색트리의 차이점으로 볼 수 있지않을까 생각해봤습니다.

완전 이진 트리는 트리의 최하위 레벨까지 모든 레벨이 다 채워져있는 트리이고, 힙이 사용하는 이진 탐색 트리는 각 부모 노드를 기준으로 해당 부모 노드보다 작으면 좌측, 부모 노드보다 크면 우측으로 각 노드를 배치합니다. 이러한 차이점으로 이진 탐색 트리는 해당 모든 레벨의 노드가 가득 채워져있는 상태가 될 수도 있고 안될 수도 있습니다. 또한 완전 이진 트리의 경우는 모든 노드를 채우는 것이 초점으로 맞춰져있습니다. 그렇기에 해당 노드가 부모 노드와 비교 했을 경우 더 큰지 작은지, 힙처럼 구분점이 없다고 생각하였습니다.

이러한 차이점이 존재하는데 그렇기에 빠른 데이터 탐색에는 해당 힙, 이진 탐색트리가 사용이 되고, 각 레벨마다 모든 노드가 채워져있는 완전 이진 트리의 경우 데이터를 효율적으로 저장하는 경우 사용될 수 있다고 생각합니다.

[skyriv213]

레드 블랙트리는 연산을 수행해도 해당 트리의 균형이 어긋나지 않는 트리입니다. 이때 균형을 유지하기 위해 사용하는 것이 기존 트리에서 속성을 추가해서 진행합니다. 속성은 이름에서 알 수 있듯이 빨간색과 검은색을 가지고 있습니다. 루트 노드와 리프노드는 검은색, 자식노드들은 빨간색을 가지고 있습니다. 노드의 색상이 빨간색이면 해당 노드의 자식은 검은색을 가지고 있습니다.

균형을 유지하기 위해서 레드 블랙 트리는 삽입 및 삭제 시 회전과 색상변경의 로직을 통해 균형을 유지합니다. 회전의 경우 각 노드의 위치를 서로 바꿔주는 로직이고, 색상변경의 경우 동일한 색상이 연속해서 발생하는 경우 해당 노드와 부모노드의 색상을 조절하는 로직입니다.

삽입 및 삭제 시 추가적인 연산을 통해 최악의 경우에도 시간복잡도를 O(logn)을 유지한다는 장점이 있습니다. 다만 기존의 트리에서 속성과 추가된 로직이 존재하기에 구현의 복잡성이 단점으로 생각됩니다.