본문 바로가기

RBTree1

[Week05] C언어 - Red Black Tree Red - Black Tree 레드 블랙 트리 https://ko.wikipedia.org/wiki/레드-블랙_트리 레드-블랙 트리 - 위키백과, 우리 모두의 백과사전 레드-블랙 트리(red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조다. 1978년 레오 귀바스(Leo J. Guibas)와 로버트 ko.wikipedia.org 이진 탐색트리의 한 종류 BTS의 worst case의 단점을 개선 - 스스로 균형을 맞추며 편향된 트리가 되지않도록 한다. 최악의 경우에도 시간복잡도가 O(logN) 규칙 레드와 블랙으로만 이루워진다. 루트 노드는 블랙이다. nil노드는 블랙이다. 레.. 2022. 5. 5.

이전 1 다음

티스토리툴바