Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 10 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 10 Prof. Erik Demaine
Balanced search trees Balanced search tree. a search-tree data structure for which a height of o(g n)is guaranteed when implementing a dynamic set of n items avl trees 2-3 trees Examples: 2-3-4 trees ●B- trees ●Red- black trees o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.2 Balanced search trees Balanced search tree: A search-tree data structure for which a height of O(lg n) is guaranteed when implementing a dynamic set of n items. Examples: • AVL trees • 2-3 trees • 2-3-4 trees • B-trees • Red-black trees
Red black trees This data structure requires an extra one- bit color field in each node Red-black properties I. Every node is either red or black 2. The root and leaves(nil's)are black 3. If a node is red then its parent is black 4. All simple paths from any node x to a descendant leaf have the same number of black nodes= black-height(x) o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.3 Red-black trees This data structure requires an extra onebit color field in each node. Red-black properties: 1. Every node is either red or black. 2. The root and leaves (NIL’s) are black. 3. If a node is red, then its parent is black. 4. All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x)
Example of a red-black tree 7 18 NILNIL 10 h=4 26 NIL NIL NILNIL NIL NIL o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.4 Example of a red-black tree h = 4 88 1111 1010 1818 2626 2222 33 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL
Example of a red-black tree 7 18 NILNIL 10 26 NIL NIL NILNIL NIL NIL 1. Every node is either red or black o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.5 Example of a red-black tree 88 1111 1010 1818 2626 2222 33 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL 1. Every node is either red or black
Example of a red-black tree 7 18 NILNIL 10 26 NIL NIL NILNIL NIL NIL 2. The root and leaves(NILs)are black o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.6 Example of a red-black tree 88 1111 1010 1818 2626 2222 33 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL 2. The root and leaves (NIL’s) are black
Example of a red-black tree 7 18 NILNIL 10 26 NIL NIL NILNIL NIL NIL 3. If a node is red then its parent is black o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.7 Example of a red-black tree 88 1111 1010 1818 2626 2222 33 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL 3. If a node is red, then its parent is black
Example of a red-black tree 7)bh=2 18)bh=2 NILNIL b=1(10 bh=1(8 26 hh=0 NILNIL NIL NIL NIL NIL 4. All simple paths from any node x to a descendant leaf have the same number of black nodes black-height(x) o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.8 Example of a red-black tree 4. All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x). 88 1111 1010 1818 2626 2222 33 77 NIL NIL NIL NIL NIL NIL NIL NIL NIL bh = 2 bh = 1 bh = 1 bh = 2 bh = 0
Height of a red-black tree Theorem. a red-black tree with n keys has height h≤21g(n+1) Proof. (The book uses induction. Read carefully. INTUITION. Merge red nodes into their black parents o 2001 by Charles E Leiserson Introduction to Algorithms Day 18 L10.9
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.9 Height of a red-black tree Theorem. A red-black tree with n keys has height h ≤ 2 lg(n + 1). Proof. (The book uses induction. Read carefully.) INTUITION: • Merge red nodes into their black parents
Height of a red-black tree Theorem. a red-black tree with n keys has height h≤21g(n+1) Proof. (The book uses induction. Read carefully. INTUITION. Merge red nodes into their black parents o 2001 by Charles E Leiserson Introduction to Algorithms Day18L10.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 18 L10.10 Height of a red-black tree Theorem. A red-black tree with n keys has height h ≤ 2 lg(n + 1). Proof. (The book uses induction. Read carefully.) INTUITION: • Merge red nodes into their black parents