Transcript 2-3-4 Trees

CIS265/506
2-3-4 Trees
Red-Black Trees
Some of the following material is from:
Data Structures for Java
William H. Ford
William R. Topp
ISBN 0-13-047724-9
Chapter 27
Balanced Search Trees
Bret Ford
© 2005, Prentice Hall
CIS265/506: Red-Black Trees
2
2-3-4 Trees

2-3-4 Trees are a slightly less efficient than
red-black trees (next topic) but easier to code
and understand.

As in most of the self-balanced trees, they
facilitate searching, insertions and deletions
in the order of O(log N) operations
regardless of how data values are entered.
CIS265/506: Red-Black Trees
3
2-3-4 Tree Concepts

Each node has 2-4 outgoing links.



Data items in the node are stored in sorted order.


This means that there are 0-3 data items in a node.
The number of links is referred to as the order of the tree
The links may have to move depending on insertions or
deletions to the data in the node
Links refer to children that are between the data
items.


End links just compare to the nearest data item (lesser or
greater).
There will always be one more link than the number of data
items
CIS265/506: Red-Black Trees
4
2-3-4 Tree Concepts

Each node has 2-4 outgoing links.





This means that there are 0-3 data items in a node.
The number of links is referred to as the order of the tree
2-Node: [ptr, A, ptr]
3-Node: [ptr, A, ptr, B, ptr]
4-node: [ptr, A, ptr, B, ptr, C, ptr]
ptr1
< A
A
Ptr2
<B
B
ptr3
< C
CIS265/506: Red-Black Trees
C
ptr4
> C
5
2-3-4 Tree Concepts

Data items in the node are stored in sorted order.

The links may have to move depending on insertions or
deletions to the data in the node
A < B < C
ptr1
A
Ptr2
B
ptr3
CIS265/506: Red-Black Trees
C
ptr4
6
2-3-4 Tree Concepts

Outgoing Links refer/point to children that are
between the data items.

End links just compare to the nearest data item (lesser or
greater).

There will always be one more link than the number of data
items
CIS265/506: Red-Black Trees
7
2-3-4 Tree Concepts

A Split refer to the process where a full node is
broken into two and a value is propagated up to its’
parent (or a new parent is made).

The details of the Split process are as follows





A new node is created that will be the sibling of the node
to be split
Move the last item into the new node
Item A is left as is
The rightmost two children are attached to the new node
Item B is moved up one level
CIS265/506: Red-Black Trees
8
2-3-4 Tree Concepts

Searching
Finding data in a 2-3-4 tree is just like searching in a binary tree
so long as order is 2. (left brach < node & right branch > node).
node
<
>
left
right
Otherwise, we need to search each of the data items in the node
until we find one greater than the value we are looking at or
reach the end. If the former occurs, take the previous link. Else,
take the last link
CIS265/506: Red-Black Trees
9
2-3-4 Tree Concepts

Inserting into a 2-3-4 Tree can be fairly easy
or hard, depending on the condition of the
nodes on the way to this node



If all the nodes on the path are not full, we just need to
traverse the tree and insert the data at the leaf level
If the nodes on the way are full, we split the node and
continue
if the leaf is full then we split that and move the middle
value up
CIS265/506: Red-Black Trees
10
2-3-4 Trees

In a 2-3-4 tree,



a 2-node has two children and one value,
a 3-node has 3 children and 2 values, and
a 4-node has 4 children and 3 values.
CIS265/506: Red-Black Trees
11
Searching a 2-3-4 Tree



To find a given value called item, start at the
root and compare item with the values in the
existing node.
If no match occurs, move to the appropriate
sub-tree.
Repeat the process until you find a match or
encounter an empty sub-tree.
CIS265/506: Red-Black Trees
12
Searching a 2-3-4 Tree
CIS265/506: Red-Black Trees
13
Inserting into a 2-3-4 Tree

New data items are always inserted in leaves at the
bottom of the tree.

To insert a new item, move down the tree, splitting any
4-node encountered in the insertion path.

Split a node by moving its middle element up one level
and creating two new 2-nodes descendants (this
includes splitting the root if it is a 4-node – see next
figure).
CIS265/506: Red-Black Trees
14
Inserting into a 2-3-4 Tree
(continued)

Splitting a 4-node.
CIS265/506: Red-Black Trees
15
Inserting into a 2-3-4 Tree
(continued)
Insert into a 2-3-4-tree the following data
values:
2, 15, 12, 4, 8, 10, 25, 35, 55, 11
CIS265/506: Red-Black Trees
16
Building a 2-3-4 Tree
Insert: 2, 15, 12
Insert: 4
Insert: 8, 10
CIS265/506: Red-Black Trees
17
Building a 2-3-4 Tree (continued)
Insert: 25, 35
Insert: 55
CIS265/506: Red-Black Trees
18
Building a 2-3-4 Tree (continued)
Insert: 55
CIS265/506: Red-Black Trees
19
Building a 2-3-4 Tree (concluded)
Insert: 11
12
12
4
2
8
4
25
10
15
35
55
2
Split 4-node (4, 12, 25)
8
25
10 11
15
35
55
Insert 11
CIS265/506: Red-Black Trees
20
Efficiency of 2-3-4 Trees

In a 2-3-4 tree with n elements, the maximum
number of nodes visited during the search for
an element is log2 (n) + 1.

Inserting an element into a 2-3-4 tree with n
elements requires splitting no more than
log2n + 1 4-nodes and normally requires far
fewer splits.
CIS265/506: Red-Black Trees
21
Red-Black Trees



A red-black tree is a binary search tree in which
each node has the color attribute BLACK or RED.
It was designed as a representation of a 2-3-4 tree,
using different color combinations to describe the
3-nodes and 4-nodes.
It is a type of tree that maintains balance via a set of
four rules and associated operations to enforce
those rules.

“intelligent” work is done as nodes are inserted as well as
when they are deleted
CIS265/506: Red-Black Trees
22
The Four Rules




Every node in the tree is colored red or black
The root is always colored black
If a node is red its children are always black
Every path to all leaves (filled or waiting to be
filled) must go through the same number of
black nodes
CIS265/506: Red-Black Trees
23
Red-Black Trees
CIS265/506: Red-Black Trees
24
Representing 2-3-4 Tree Nodes


A 2-node is always black.
A 4-node has the middle value as a black
parent and the other values as red children.
CIS265/506: Red-Black Trees
25
Representing 2-3-4 Tree Nodes
(concluded)

Represent a 3-node with a BLACK parent
and a smaller RED left child or with a BLACK
parent and a larger RED right child.
3-node (A, B)
in a 2-3-4 Tree
(a) Red-black tree representation
A is a black parent; B is a red right child
A
A B
B
S
S
T
(b) Red-black tree representation
B is a black parent; A is a red left child
U
A
B
U
T
U
CIS265/506: Red-Black Trees
S
T
26
Representing a 2-3-4 Tree as a
Red-Black Tree
CIS265/506: Red-Black Trees
27
Properties of a Red-Black Tree

These properties follow from the
representation of a 2-3-4 tree as a
red-black tree.



Root of red-black tree is always BLACK.
A RED parent never has a RED child. Thus in a
red-black tree there are never two successive
RED nodes.
Every path from the root to an empty subtree
contains the same number of BLACK nodes. The
number, called the black height, defines balance
in a red-black tree.
CIS265/506: Red-Black Trees
28
Inserting a Node in a Red-Black
Tree (continued)



Enter a new element into the tree as a RED
leaf node.
Inserting a RED node at the bottom of a tree
may result in two successive RED nodes.
When this occurs, use a rotation and
recoloring to reorder the tree.
Maintain the root as a BLACK node.
CIS265/506: Red-Black Trees
29
Building a Red-Black Tree
CIS265/506: Red-Black Trees
30
Building a Red-Black Tree
(continued)
CIS265/506: Red-Black Trees
31
Building a Red-Black Tree
(concluded)
Insert 30
CIS265/506: Red-Black Trees
32
Red-Black Tree Search Running
Time

The worst-case running time to search a redblack tree or insert an item is O(log2n).

The maximum length of a path in a red-black tree
with black height B is 2*B-1.
CIS265/506: Red-Black Trees
33
Note
There is no code in your text for this
structure.
CIS265/506: Red-Black Trees
34