Description

Description:

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Transcript

Lecture Notes onRed/Black Trees
15-122: Principles of Imperative ComputationFrank PfenningLecture 17October 21, 2010
1 Introduction
In this lecture we discuss an ingenious way to maintain the balance invari-ant for binary search trees. The resulting data structure of
red/black trees
isused in a number of standard library implementations in C, C++, and Java.
2 Three Invariants
Ared/blacktreeisabinarysearchtreeinwhicheachnodeiscoloredeitherred or black. At the interface, we maintain three invariants:
Ordering Invariant
This is the same as for binary search trees: all the keysto left of a node are smaller, and all the keys to the right of a node arelarger than the key at the node itself.
Height Invariant
The number of
black
nodes on every path from the rootto each leaf is the same. We call this the
black height
of the tree.
Color Invariant
No two consecutive nodes are red.The balance and color invariants together imply that the longest path fromthe root to a leaf is at most twice as long as the shortest path. Since insertand search in a binary search tree have time proportional to the length of the path from the root to the leaf, this guarantees
O
(log(
n
))
times for theseoperations, even if the tree is not perfectly balanced. We therefore refer tothe height and color invariants collectively as the
balance invariant
.
L
ECTURE
N
OTES
O
CTOBER
21, 2010
Red/Black Trees L17.2
3 Insertion
The trick is, of course, to maintain all three invariants while sticking to thelogarithmictimeboundforeachinsertandsearchoperation. Searchiseasy,sincethesearchalgorithmdoesnotrequirethenodecolors: itworksexactlyas for the general case of balanced binary trees.Insertion, however, is not obvious. Let’s try just following the usualalgorithm for insertion. We compare the key of the new element with thekey at the root. If it is equal, we replace the current element. If it is less werecursively insert into the left subtree. If it is greater, we recursively insertinto the right subtree. Below is a concrete example.
! !$ !% ! !& ' ( )*+ ,-+* ./012 ,-+* ./012 3*4536 7 8 1-/-) 4,9: ;0<;=*+
If we want to insert a new element with a key of
14
, the insertion algorithmsketched above would put it to the right of
13
. In order to preverse the
L
ECTURE
N
OTES
O
CTOBER
21, 2010
Red/Black Trees L17.3
height invariant, we must color the new node red.
! # %&# '()*+ %&# '()*+ , -.,/ 0 1 *&(&! -%23 4)546 # 78 79 7: 7 7; < = 7=
Both color and height invariants are still satisﬁed, as is the ordering invari-ant (which we always preserve).Now consider another insertion, this time of an element with key
15
.This is inserted to the right of the node with key
14
. Again, to preserve theheight invariant we must color it red, but this violates the color invariantsince we have to adjacent red nodes.
! # %&# '()*+ %&# '()*+ , -.,/ 0 1 *&(&! -%23 2-&()/ # )/ 45647 48 49 4: 4 4; < 5 45 47
In order to restore the color invariant between
14
and
15
we can apply a
leftrotation
, moving
14
up in the tree and
13
to the left. At the same time we
L
ECTURE
N
OTES
O
CTOBER
21, 2010
Red/Black Trees L17.4
recolor
15
to be black, so as to remove the color conﬂict while preservingthe black height invariant. However, we introduce a new color conﬂict between
14
and its parent.
! #$% '()*'+ , - $. ./ )012 /(3+./(4 #+ 56758 $. ./ )012 1). #+(4 #+ 59756 59 5: 5; 5 56 < 6 58 5=
Now we can apply a right rotation, moving
14
up one level, immediatelyfollowed by a left rotation, moving
14
up to the root.
! !$ !% ! !& ' & !( !) ! !$ !% ! !& ' & !( !)
Such a sequence of two rotations is called a
double rotation
. The result nowsatisﬁes the height invariant (still with height 2) and the color invariant.We can apply one further simple step, which is to recolor the root to black. Thisincreasestheblackheightoneverypathfromtherootbyone,soit preserves the height invariant. Generally speaking, the fewer red nodes
L
ECTURE
N
OTES
O
CTOBER
21, 2010

Search

Similar documents

Tags

Related Search

Massive Sequencing and Microarray PdfMaterial Caracterization X ray (SAXS WAXS PDFPeransertamasyarakat.pdfTypes of Construction Contracts Pdfpdf Filsafat dari persfektif kristianiDownload PDFDesain UML Sistem Informasi Absensi.pdf16-Aksoy-Halifelik.pdf2013-jadi-buku-filsafat-ilmu.pdfEngineering Surveying, 5th Ed 0750649879.pdf

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x