CS计算机代考程序代写 data structure AVL algorithm COMP2100/COMP6442

COMP2100/COMP6442
Data Structures Part II
– Lecture 3]
Kin Chau [
Sid Chi
1

Recap from Previous Lecture
• Binary search tree
• At most two children for each node
• Left child node is smaller than its parent node
• Right child node is greater than its parent node
• Can support dynamic set operations
• Search, Minimum, Maximum, Predecessor, Successor, Insert, and Delete
56
26
200
18
28
190
213
24
2

Worse
• Insert 6, 5, 4, 3, 2, 1 in an empty tree in order • Depth of tree linear increases
6 5
–
case Scenario
4 3
4
26 135
Balanced tree
2 1
Unbalanced tree
3

Balanced Tree
• Balanced search tree
• Belong to binary search tree
• But with a height of O(log(n)) guaranteed for n items
• Height h = maximum number of edges from the root to a leaf
• Examples
• Red-black tree • AVL tree
• B-tree
h ≈ log(n)
4

Goals of This Lecture
• Red-black tree
• Balanced tree by coloring the nodes
• AVL tree is similar to red-black tree • B-tree
• Balanced tree by keeping all leaves at same level
• Something else to learn
• Applications of different data structures
5

Red
• Close to balanced tree
• Tree structure requires an extra one-bit color field in each node: either red or black
–
Black Tree
• Color is used to maintain balance in an approximate sense
• Node: • Key
• Color • Left •Right • Parent
4
26 1 35
• Note: Leave nodes are NULL nodes (with no child)
6

–
Black Properties
Red
• The red-black properties:
1. Every node is either red or black
2. (a) Root and (b) leaves (NULL node) are black
• Note: this means every “real” node has 2 children 3. If a node is red, both children are black
• Note: cannot have 2 consecutive reds on a path
4. Every path from node to descendent leaf contains the same
number of black nodes
• “Black-height” is the number of black nodes on a path to a leaf
• Red-black property #4 ensures the black-height is independent of any leaf
7

Example
• The red-black properties:
1. Every node is either red or black
2. Root and leaves (NULL node) are black
3. If a node is red, both children are black
4. Every path from node to descendent leaf contains the same number of black nodes
• Add a new node with x.key = 8
7
59 8
12
9

Red
• Insertion: the basic idea
• Insert the new node as in binary search tree
• Color the new node red
• Only red-black property #3 may be violated
• It will be violated if the new node’s parent is red
• If so, move violation up the tree until a place is found where it can be fixed
–
Black Tree Insertion
12

Example
• Insertion:
• Insert the new node as in binary search tree • Color the new node red
• Add a new node with y.key = 11 • Insert y as in binary search tree
• Set y.color  ???
7
59 8
12 11
13

Example
• Insertion:
• Insert the new node as in binary search tree • Color the new node red
• Add a new node with y.key = 11 • Insert y as in binary search tree
• Set y.color  red • Recolor the tree
7
59 8
12 11
14

Example
• Insertion:
• Insert the new node as in binary search tree • Color the new node red
• Add a new node with z.key = 10 • Insert z as in binary search tree
• Set z.color  red
7
59 8
12
11 10
15

Example
• Insertion:
• Insert the new node as in binary search tree • Color the new node red
• Add a new node with z.key = 10 • Insert z as in binary search tree
• Set z.color  ??
• Tree is too unbalanced
• Need to restructure
• See how to deal with it next …
7
59 8
12
11 10
16

Tree Rotation
• Our basic operation for changing tree structure is called rotation • Rotation preserves inorder key ordering
• How would tree rotation actually work?
y rightRotate(y) x xC Ay
A B leftRotate(x) B C
17

Tree Rotation
• Need a couple of pointer manipulations • x keeps its left child
• y keeps its right child
• x’s right child becomes y’s left child • x’s and y’s parents change
y rightRotate(y) x xC Ay
A B leftRotate(x) B C
18

Example
• Left Rotate at node 9 7
leftRotate(x) 7
x
5 9y5x12
812 9
11 811
y
19

Three Possible Cases
• Suppose that the parent of the new node is the left child of its grandparent
• “Uncle” is the other child of the grand parent
• Cases:
1. New node z’s uncle is red
2. New node z is right child and its uncle is black
3. New node z is left child and its uncle is black
Case 1 Case 2 zzz
z’s grandparent
z’s parent
z’s uncle
z
Case 3
20

Mirrored Possible Cases
• Cases:
1. New node z’s (right) uncle is red
2. New node z is right child and its uncle is black
3. New node z is left child and its uncle is black
4. New node z’s (left) uncle is red
5. New node z is left child and its uncle is black
6. New node z is right child and its uncle is black
Case 4 Case 5
z z 21z
Case 6

Red
• Case 1: Uncle is red • Solution: Recoloring
• Assume all subtree ’s have equal black-height
• Recolor parent, uncle y and grandparent to satisfy the property that all
paths have equal black height
• Note: If c is root, then reset the color to be black at the end of insertion
–
Black Tree Insertion: Case 1
// Case 1
If (y.color = RED) Then z.parent.color  BLACK y.color  BLACK z.parent.parent.color  RED
c ay
Recolor
c ay


z 


z

22

Red
• Case 1: Uncle is red
• Solution: Recoloring
• New node z can be either left or right child
–
Black Tree Insertion: Case 1
// Case 1
If (y.color = RED) Then z.parent.color  BLACK y.color  BLACK z.parent.parent.color  RED
c ay
Recolor
c ay
zz


23

Red
• Case 2: Uncle is black
• New node z is right child • Solution: Transformation
• Transform to case 3 via a left-rotation
–
Black Tree Insertion: Case 2
// Case 2
If (z = z.parent.right) Then z  z.parent
leftRotate(z)
// continue with Case 3
c

Move Pointer
z
c
leftRotate
c
Case 3


 
zz
24

–
Black Tree Insertion: Case 3
Red
• Case 3: Uncle is black
• New node z is left child • Solution: Rotation
• Recolor and right rotate c
Case 3
a zc

// continue with Case 3
z.parent.color  BLACK z.parent.parent.color  RED rightRotate(z.parent.parent)

 
z

a
25

Example
• Let us return to the example
• Add a new node with z.key = 10 • Which Case is it?
• It is Case 3
• Recolor and rotate right
7
59 8
12
11 10
26

Example
• Let us return to the example
• Add a new node with z.key = 10 • Which Case is it?
• It is Case 3
• Recolor and rotate right
7
59 8
11
10
12
27

Red
• Cases:
1. New node z’s (right) uncle is red
2. New node z is right child and its uncle is black
3. New node z is left child and its uncle is black
4. New node z’s (left) uncle is red
5. New node z is left child and its uncle is black
6. New node z is right child and its uncle is black
• Cases 1-3 hold if z’s parent is a left child of its grandparent • If z’s parent is a right child of its grandparent, Cases 4-6 are
symmetric to Cases 1-3
• Swap left for right, and vice versa
–
Black Tree Insertion: Cases 4
–
6
28

Red
–
Black Tree Insertion
RB-InsertFixup[T,z]
While z.parent.color = RED Do
If z.parent = z.parent.parent.left Then
y  z.parent.parent.right // Case 1
If (y.color = RED) Then
z.parent.color  BLACK y.color  BLACK z.parent.parent.color  RED // Continue While loop
z  z.parent.parent Else
If (z = z.parent.right) Then // Case 2
z  z.parent
leftRotate(z)
// continue with case 3
z.parent.color  BLACK z.parent.parent.color  RED rightRotate(z.parent.parent)
Else
// Cases 4-6 with “right” & “left” exchanged
T.root.color  BLACK
29
RB-Insert[T,z]
// Call BST-Insert
BST-Insert[T,z]
z.left  null; z.right  null
z.color  RED
// Call RB-InsertFixup to
// recolor and restructure tree RB-InsertFixup[T,z]

Exercise
• Consider the following operations to red-black tree • Insert 12, 43, 34, 11, 44, 1
• What is the tree height of the final tree?
• How many red nodes are in the final tree?
30

Red
• x is the to-be-deleted node (disregarding the colors):
–
Black Tree Deletion
• Cases:
x
y
1.
x has only one child
• Just remove x and replace x by its child
2.
• If the red-black property #3 is now broken, recolor y in black keeping the black-height, since x was definitely black (as its parent is red)
x has two children
x uy
31

Red
• Cases:
–
Black Tree Deletion
2.
x has two children, x’s successor is z
• Replace the successor z by left child w
• Remove x and replace x by its successor z
• But if x is red and z is black, then there will be an extra black node in z’s new left child
x uy z
w
z uy w
• See Chapter 14 of “Introduction to Algorithms” (by Cormen, Leiserson and Rivest)
32

Black
• The red-black properties:
1. Every node is either red or black
2. Root and leaves (NULL node) are black
3. If a node is red, both children are black
–
height
Root
Leaf
4. Every path from node to descendent leaf contains the same number of black nodes
• Let black-height (BH(x)) be the number of black nodes from x to a leaf • BH(x) is independent of any leaf node
• Note: No adjacent nodes on any path on red-black tree can be both red • Otherwise, it violates red-black property #3
7 9 11 12
33

Quick Fact
• Note that Black-height  tree height
• Let the “internal” nodes be non-leaf nodes
• Consider the extreme case:
• All nodes are black (ignoring all red nodes)
• The tree is perfectly balanced
• Check: satisfy all red-black properties
• Total number of black internal nodes is 20+21+22+ … + 2BH(root)-1 = 2BH(root) – 1
• Hence,
• Total number of internal nodes  2BH(root) – 1
• Since adding red internal nodes back will not affect the black-height
⋮⋮⋮⋮⋮⋮⋮⋮ ⋯⋯⋯⋯⋯⋯⋯⋯⋯
34
Black-height

Red
• What is the minimum black-height of the root with height h?
• Answer: BH(root)  h/2
• Because the number of black nodes from the root to a leaf is at least h/2 • Otherwise, two red nodes will be adjacent to each other
–
Black Tree: Worst
–
case
Running Time
Theorem: A red-black tree with n internal nodes has height h  2 log(n + 1) Proof: Note that n  2BH(root) – 1
Since BH(root)  h/2, we obtain n2BH(root)-12h/2 -1
 n2h/2 -1
Then, log(n + 1)  h/2  h  2 log(n + 1)
Therefore, h = O(log(n))
35

Red
• So we have shown that a red-black tree has O(log(n)) height
• Corollary: These operations take O(log(n)) time • Minimum, Maximum
• Successor, Predecessor
• Search
• Insert and Delete
• Will also take O(log(n)) time
• But will need to take special care since they modify tree structure
–
Black Tree: Worst
–
case
Running Time
36

Demo
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
37

Implement a Red
–
Black Tree
public class RBTree > {
private void insert(Node x) { … }
public void rotateLeft(Node x) { … }
public void rotateRight(Node x) { … }
public Node search(T key) { }
public class Node {
Colour colour; // Node colour
T key; // Node value
Node parent; // Parent node Node left, right; // Child nodes
}
38

Summary
• Balanced search tree • Red-black tree
• Red-black properties • Insertion
• Black-height
7
9
5
8
12
39

Reference
• Visualizations
• https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
• Reference:
• Chapter 14 in Introduction to Algorithms (by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest)
40

Related Posts