程序代写代做代考 algorithm B tree Haskell data structure Red-Black Trees

Red-Black Trees
Advanced Algorithms and Data Structures – Lecture 3
Venanzio Capretta Thursday 22 October 2020
School of Computer Science, University of Nottingham

BST: Keeping the Balance
Binary Search Trees implement the basic operations of Dynamic Sets in O(h) time, where h is the height of the tree
If the tree is balanced, h = O(log n) where n is the number of elements However, there is no guarantee that the tree is balanced
The operations insert and delete can change the balance of the tree
For an efficient representation we must
implement insert and delete so that they preserve the balance Not easy
There are several ways to do it
1

Red-Black Trees Definition
Idea:
• Color the nodes of a BST either Red or Black
• When computing the height, only count black nodes
• Keep the number of red nodes low: no consecutive red nodes
A Red-Black Tree is a BST satifying these properties:
1. Every node contains and extra color value: Red or Black (basically a Boolean value)
2. The root (and leaves) are black
3. The children of a red node are black
(no consecutive red nodes)
2

Example of Red-Black Tree
Example (red nodes have double circles)
4
3 11
1 􏰀 7 13 􏰀􏰀69􏰀􏰀
􏰀􏰀􏰀􏰀
3

Example of Red-Black Tree
Example (red nodes have double circles)
4
3 11
1 􏰀 7 13 􏰀􏰀69􏰀􏰀
􏰀􏰀􏰀􏰀
All paths from root to a leaf contain two black nodes: black-height = 2
• Shortest paths: only black nodes, eg: 4, 3, ·
• Longest paths: alternating black and red , eg: 4, 11, 7, 9, ·
3

Example of Red-Black Tree
Example (red nodes have double circles)
4
3 11
1 􏰀 7 13 􏰀􏰀69􏰀􏰀
􏰀􏰀􏰀􏰀
All paths from root to a leaf contain two black nodes: black-height = 2 • Shortest paths: only black nodes, eg: 4, 3, ·
• Longest paths: alternating black and red , eg: 4, 11, 7, 9, · Longest paths at most twice as long as shortest
3

Definition of Data Type
Definition of the type of Red-Black trees in Haskell Similar to Binary Search Trees, with extra field for color
data Color = Red | Black
data RBTree = Leaf | Node Color RBTree Key RBTree
The term (Node Red t1 x t2) represents the tree x
t1
Type definition does not guarantee elements are correct Red-Black trees
Ensure that the properties are satisfied when you create and modify trees: The element must be a correct Binary Search Tree and
It must satisfy the extra Red-Black properties
t2
4

Height of Trees
If a R-B tree contains n elements, then
the maximum length of a path is 2 log(n + 1)
Even if the tree is not perfectly balanced, its height is O(logn) Therefore the running time for searching is O(logn)
But we must modify the insertion and deletion algorithms to preserve the R-B properties
Idea:
• Insert and delete as for regular binary search trees • Always color new nodes red when you insert
• Rotate and recolor to restore the properties
5

Balance Rotation I
Assume that the top node is black,
but there are two consecutive red nodes under it
There are four cases, according to the position of the red nodes
First Case:
x3 x2
x1
t4 t3
t1
t2
BSTproperty: t1 x=balancecolort1x(insat2) | otherwise = t
9

Insertion
Insert a new element into a R-B tree by:
• Insert in place of a leaf as in BSTs
• Initially color the new node red
• Recursively apply balance to fix consecutive reds • At the end, if the root is red, make it black
ins :: Key → RBTree → RBTree ins a Leaf = Node Red Leaf a Leaf ins a t@(Node color t1 x t2)
| ax=balancecolort1x(insat2) | otherwise = t
The result satisfies most the R-B properties, Except: Its root could be red (and might have a red child)
9

Insertion
Insert a new element into a R-B tree by:
• Insert in place of a leaf as in BSTs
• Initially color the new node red
• Recursively apply balance to fix consecutive reds • At the end, if the root is red, make it black
ins :: Key → RBTree → RBTree ins a Leaf = Node Red Leaf a Leaf ins a t@(Node color t1 x t2)
| ax=balancecolort1x(insat2) | otherwise = t
The result satisfies most the R-B properties, Except:
Its root could be red (and might have a red child) – just paint it black:
insert :: Key → RBTree → RBTree insert a tree = blackRoot (ins a tree)
9

Insert Observations
Let’s say that a tree is weakly R-B if it satisfies all the R-B properties except that its root may be red and one of its children may also be red (so there could be two consecutive red nodes at the top).
Observation:
• If t is a weakly R-B tree, then also (ins a t) is a weakly R-B tree
• If t is a weakly R-B tree, then we can turn it into a fully R-B tree by painting its root black
This will increase the black-height by one,
but since we do it at the root,
all paths will increase their black-lenghts equally.
10

Complexity of Insert
The function balance only rearranges the first two levels of the tree, So it runs in constant time
11

Complexity of Insert
The function balance only rearranges the first two levels of the tree, So it runs in constant time
So insert still runs in O(h) time where h is the height of the tree
11

Complexity of Insert
The function balance only rearranges the first two levels of the tree, So it runs in constant time
So insert still runs in O(h) time where h is the height of the tree
The height of a R-B tree is h = O(log n)
11

Deletion
Deleting an element is a bit more complicated than inserting it Deletion may cause a subtree to decrese its black-height
Then we must apply some rotations to rebalance it
12

Deletion
Deleting an element is a bit more complicated than inserting it Deletion may cause a subtree to decrese its black-height
Then we must apply some rotations to rebalance it
For example, if we delete x from the tree
y
in the case that x < y, we delete it from t1 This may cause the black-height of t1 to decrease while the black-height of t2 is unchanged t1 t2 12 Deletion Deleting an element is a bit more complicated than inserting it Deletion may cause a subtree to decrese its black-height Then we must apply some rotations to rebalance it For example, if we delete x from the tree y t1 t2 in the case that x < y, we delete it from t1 This may cause the black-height of t1 to decrease while the black-height of t2 is unchanged Define rebalancing functions for when one child has a black-height larger by one than the other 12 Delete: Simultaneously Defined Functions 13 Delete: Simultaneously Defined Functions • delete :: Key -> RBTree -> RBTree
(delete x t) looks for key x in the tree t; if it finds it, it deletes it and rebalances the tree so the R-B properties hold
13

Delete: Simultaneously Defined Functions
• delete :: Key -> RBTree -> RBTree
(delete x t) looks for key x in the tree t; if it finds it, it deletes it and rebalances the tree so the R-B properties hold
• del :: Key -> RBTree -> RBTree
Preliminary version of delete: the result satisfies the R-B properties except it may have two consecutive red nodes at the top
• delL :: Key -> RBTree -> RBTree Deletes an element from the left child
• balL :: Key -> RBTree -> RBTree
Rebalances a tree when the black-height of the left child is one shorter than the right
13

Balancing Left I
Suppose we have a tree in which the black-height of the left child is one less than the black-height of the right child
There can be three cases (color of the root irrelevant or obvious) First Case (left child has a red node):
y
x
t3
t1
t2
y must be black We swap the colors of x and y
The black-height of the left child increases by 1,
the black-height of the right child is unchanged
(There could now be two red nodes at the top) 14

Balancing Left II
Second Case (left child black or leaf, right black):
y
􏰀
t1
z
t2
t3
15

Balancing Left II
Second Case (left child black or leaf, right black):
y
􏰀
t1
z
Just repaint z red
t2
t3
15

Balancing Left II
Second Case (left child black or leaf, right black):
y
􏰀
z
t1
t2
Just repaint z red
We decreased the black-height of the right child
t3
15

Balancing Left II
Second Case (left child black or leaf, right black):
y
􏰀
z
t1
t2
Just repaint z red
We decreased the black-height of the right child
But we may have created consecutive red nodes on the right
t3
15

Balancing Left III
Third Case (left child black or leaf, right red):
y
􏰀
z
t1
u
􏰀
t4
t3
There must be at least a black node under z for the right child to have higher black-height
t4 must have a black top node
t2
16

Balancing Left III
Third Case (left child black or leaf, right red):
u
yz
􏰀
t1 t2 t3 t4
There must be at least a black node under z for the right child to have higher black-height
t4 must have a black top node
We might have created consecutive red nodes in the right child Apply balance to the right child
16

Balance Left in Haskell
If we put the three cases together we obtain the function
to rebalance when the left child has black-height smaller by 1
17

Balance Left in Haskell
If we put the three cases together we obtain the function
to rebalance when the left child has black-height smaller by 1
The input tree is given in its three components No need to specify the color of the root
balL :: RBTree → Key → RBTree → RBTree balL (Node Red t1 x t2) y t3
= Node Red (Node Black t1 x t2) y t3 balL t1 y (Node Black t2 z t3)
= balance Black t1 y (Node Red t2 z t3) balL t1 y (Node Red (Node Black t2 u t3) z t4)
= Node Red (Node Black t1 y t2) u
(balance Black t3 z (redRoot t4))
17

Delete Left
Deleting a key from the left child (when x < y) 18 Delete Left Deleting a key from the left child (when x < y) If the initial top node of the child is black the deletion will decrease the black height so we must rebalance with balL 18 Delete Left Deleting a key from the left child (when x < y) If the initial top node of the child is black the deletion will decrease the black height so we must rebalance with balL Otherwise (top node red) the black-height stays the same and we don’t need to rebalance 18 Delete Left Deleting a key from the left child (when x < y) If the initial top node of the child is black the deletion will decrease the black height so we must rebalance with balL Otherwise (top node red) the black-height stays the same and we don’t need to rebalance delL :: Key → RBTree → Key → RBTree → RBTree delL x t1 y t2 = if (color t1) == Black then balL (del x t1) y t2 else NodeRB Red (del x t1) y t2 18 Delete Left Deleting a key from the left child (when x < y) If the initial top node of the child is black the deletion will decrease the black height so we must rebalance with balL Otherwise (top node red) the black-height stays the same and we don’t need to rebalance delL :: Key → RBTree → Key → RBTree → RBTree delL x t1 y t2 = if (color t1) == Black then balL (del x t1) y t2 else NodeRB Red (del x t1) y t2 Define similar functions balR and delR to rebalance and delete on the right 18 Fuse In the case when x = y, we must delete the root of the tree If we delete x from x t1 t2 We’re left with the orphan trees t1 and t2 We must put them back together into a single tree 19 Fuse In the case when x = y, we must delete the root of the tree If we delete x from x t1 t2 We’re left with the orphan trees t1 and t2 We must put them back together into a single tree The strategy that we used with Binary Search Trees of replacing the deleted node with the minimum of the right child doesn’t work any more, because it may disrupt the R-B properties 19 Fuse In the case when x = y, we must delete the root of the tree If we delete x from x t1 t2 We’re left with the orphan trees t1 and t2 We must put them back together into a single tree The strategy that we used with Binary Search Trees of replacing the deleted node with the minimum of the right child doesn’t work any more, because it may disrupt the R-B properties We must come up with a cleverer way of fusing t1 and t2 fuse :: RBTree -> RBTree -> RBTree
We know that all elements of t1 are smaller than all elements of t2
19

Fuse: Different Color
If the two trees have top nodes of different color t1=􏰀 t2=y
t1
t3 t4 We can choose the red one as new top node
20

Fuse: Different Color
If the two trees have top nodes of different color
y
fuset1 t3
We can choose the red one as new top node
t4
20

Fuse: Different Color
If the two trees have top nodes of different color
y
We can choose the red one as new top node
fuset1 t3
Similarly when the first is red and the second is black
t4
20

Fuse: Both Red
If both trees have a red top node
t1= x t2= y
t3 t4 t5 t6
21

Fuse: Both Red
If both trees have a red top node
t1= x t2= y
t3 t4 t5 t6 First we recursively fuse the middle subtrees: s =fuset4 t5
21

Fuse: Both Red
If both trees have a red top node
t1 = x t2 = y fuset4 t5 =
􏰀
s
t3 t4 t5 t6
First we recursively fuse the middle subtrees: s =fuset4 t5 If s has a black top node,
21

Fuse: Both Red
If both trees have a red top node
x
y
t3
􏰀
s t6
First we recursively fuse the middle subtrees: s =fuset4 t5 If s has a black top node, we put it under y
21

Fuse: Both Red
If both trees have a red top node
t1= x t2= y s= z
t3 t4 t5 t6 s1 s2
First we recursively fuse the middle subtrees: s =fuset4 t5 If s has a red top node,
21

Fuse: Both Red
If both trees have a red top node
z xy
t3 s1 s2 t6 First we recursively fuse the middle subtrees: s =fuset4 t5
If s has a red top node, we use its node as new root
There are double red nodes on both sides, but
the top node will be recolored black either by balL or balR or delete, according to where we deleted: left, right, or root
21

Fuse: Both Black
If both trees have a black top node
t1= x t2= y
t3 t4 t5 t6
22

Fuse: Both Black
If both trees have a black top node
t1= x t2= y
t3 t4 t5 t6 Again we recursively fuse the middle subtrees: s = fuse t4 t5
22

Fuse: Both Black
If both trees have a black top node
t1 = x t2 = y fuset4 t5 =
􏰀
s
t3 t4 t5 t6
Again we recursively fuse the middle subtrees: s = fuse t4 t5 If s has a black top node,
22

Fuse: Both Black
If both trees have a black top node
x
y
t3
􏰀
s t6
Again we recursively fuse the middle subtrees: s = fuse t4 t5
If s has a black top node, we put it under y
But this time the right subtree has increased black-height We must apply balL
22

Fuse: Both Black
If both trees have a black top node
t1= x t2= y s= z
t3 t4 t5 t6 s1 s2
Again we recursively fuse the middle subtrees: s = fuse t4 t5 If s has a red top node,
22

Fuse: Both Black
If both trees have a black top node
z
xy
t3 s1 s2 t6
Again we recursively fuse the middle subtrees: s = fuse t4 t5 Ifs hasaredtopnode,weuseitasnewroot
22

The main delete function
Having defined all the auxiliary functions, we can now simply implement the main delete function:
delete :: Key → RBTree → RBTree delete x t = blackRoot (del x t)
del :: Key → RBTree → RBTree del x LeafRB = LeafRB
del x (NodeRB _ t1 y t2)
| xy = delR x t1 y t2
| otherwise = fuse t1 t2
— delete from left child
— delete from right child
— delete root, fuse children
23

Related Posts