일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 프로그래밍
- 도커
- 배포
- 라피신
- EC2
- 설계
- RDS
- 스프링부트
- 위키북스
- UNICON2023
- 인프라
- 게임개발동아리
- UNIDEV
- 생활코딩
- 프리티어
- UNICON
- 온라인테스트
- 자바개발자
- 42서울
- AWS
- CICD
- 백엔드
- 전국대학생게임개발동아리연합회
- 인디게임
- 백엔드개발자
- 체크인미팅
- 스프링
- Developer
- 자바
- 개발공부
- Today
- Total
목록2024/06/19 (2)
Hyun's Wonderwall
Red-black tree- 트리의 균형을 보장 -> 최악의 경우에도 O(lgn) 시간에 수행.- color 속성: red 또는 black. // BST에서 상속되는 속성 key, left, right, p- 리프노드(빈 트리)들은 흑색인 경계노드 T.nil. 널포인터 역할임 // T.nil.color=black.- 루트노드의 부모노드도 T.nil - key가 있으면(nil아니면) 다 내부노드, 모든 내부 노드는 자식 2개 가짐. (nil 리프는 보여지지 않을 뿐)- 맨밑 경계노드 T.nil 만이 리프노드=외부노드. 항상 흑색. RBT는 (BST에서의) NULL 대신 T.nil 가리켜 사용 레드블랙트리의 특성1. 모든 노드는 red거나 black이다.2. 루트 노드는 black이다.3. 모든 리프 노드(..
Binary Search Tree (BST, 이진검색트리)- 동적 집합 연산을 지원하는 자료구조. (search, minimum, predecessor, successor, insert, delete)- 수행시간이 트리의 높이에 비례: O(h)- 한 노드의 왼쪽, 오른쪽 자식노드도 각 서브트리의 루트가됨 -> 재귀적으로 이진탐색트리- 노드들이 연결된 자료구조. - root(T)가 T의 루트노드를 가리킨다. // p[root[T]]=NIL- null도, 노드가 1개여도 BST이다. - 각 노드가 포함하는 필드들: key, left(왼쪽 자식 노드의 포인터), right(오른쪽 자식 노드의 포인터), p(부모 노드의 포인터), satellite data(부속 데이터)- 루트 노드는 부모노드가 NIL인 유일한..