[알고리즘] 레드블랙트리(red-black tree) - 특징, 삽입

red-black tree자가 균형 이진 탐색트리로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조.트리에 n개의 원소가 있을 때 최악의 경우에도 일정한 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 한다.또, 레드-블랙 트리에서는 리프 노드들은 비어있고, 자료를 가지고 있지 않다. 1. 특징트리의 모든 노드의 색은 BLACK or RED루트 노드의 색은 무조건 BLACK 모든 리프 노드(자식이 없는 노드)의 색은 BLACK RED 노드의 자식들은 모두 BLACK , BLACK 노드의 자식들은 BLACK or RED루트 노드에서 모든 리프 노드 사이에 있는 BLACK 노드의 수는 모두 동일> BLACK 은 연달아 올 수 있지만, RED 는 연달아 올 수 없다. 2. 연산[ 회전 ] > ..
algorithm & data structure 2018. 6. 29. 15:15
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2024/12   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
글 보관함