Red Black Trees 레포트
- 등록일 / 수정일
- 페이지 / 형식
- 자료평가
- 구매가격
- 2010.07.13 / 2019.12.24
- 38페이지 / pptx (파워포인트 2007이상)
- 평가한 분이 없습니다. (구매금액의 3%지급)
- 2,800원
최대 20페이지까지 미리보기 서비스를 제공합니다.
자료평가하면 구매금액의 3%지급!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
추천 연관자료
- 목차
-
1.Introduction
-History
-related information
2.Red Black properties
3.Operations
-Insert & delete
-code samples
-running times
-Advantage & Disadvantage
-Comparison to other algorithms
4.Applications
- 본문내용
-
Introduction (1/2)
The Red Black Tree was first invented by Rudolf Bayer (1972), who called them “symmetric binary B-trees”.
In 1978, Leo J Guibas and Robert Sedgewick came up with the term, Red Black Binary Tree.
In 2008, Sedgewick introduced a simpler version of red-black trees called Left-Leaning Red-Black Trees
A RED-BLACK tree is a type of binary search tree that is self balancing.
Each node holds one extra piece of data, Color (red or black).
Besides following the rules of Binary Search Trees, Red Black Trees have 5 addition rules that keep them balanced.
Note1: leaves are nil (no value) and act just as place holder.
Note2: A Red Black Tree has a height of 2log(n + 1) at most
All rules pertaining to a Binary Search Tree.
A node is either RED or BLACK.
The root is always BLACK.
All leaves are BLACK.
Both Children of a node that is RED, are BLACK. (no RED node can have a RED child).
Every (simple) path from a node to a descendant leaf contains the same number of black Nodes (leaves not included). This is called BLACK height.
자료평가
-
아직 평가한 내용이 없습니다.