Scribd
Upload
109 views48 pages

AA-tree Lecture

The document discusses AA trees, which are a type of balanced binary search tree that is simpler to implement than red-black trees. AA trees use levels to help balance the tree and have five invariants related to levels that must be maintained. The skew and split operations are used to handle violations of the invariants during insertions and deletions.

Uploaded by

Suraj Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
109 views48 pages

AA-tree Lecture

The document discusses AA trees, which are a type of balanced binary search tree that is simpler to implement than red-black trees. AA trees use levels to help balance the tree and have five invariants related to levels that must be maintained. The skew and split operations are used to handle violations of the invariants during insertions and deletions.

Uploaded by

Suraj Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 48

CS350: Data Structures

AA Trees
YORK COLLEGE OF PENNSYLVAN

MNK
YORK COLLEGE OF PENNSYLVANIA

JHG
'@OK

12
James Moscola

Department of Engineering & Computer Science

York College of Pennsylvania

CS350: Data Structures © James Moscola


Introduction to AA Trees

• A type of balanced binary search tree

• Developed as a simpler alternative to red-black trees and other


balanced trees
- Introduced by Arne Andersson (hence the AA) in 1993

- Eliminates many of the conditions that need to be considered to


maintain a red-black tree

- Fewer conditions means AA trees are easier to implement

- Comparable in performance to red-black trees

CS350: Data Structures 2


Introduction to AA Trees

• Similar to red-black trees, but with the addition of a single new rule
- Every node is colored either red or black

- The root node is black

- If a node is red, its children must be black

- Every path from a node to a null link must contain the same number
of black nodes

- Left children may not be red

New Rule

CS350: Data Structures 3


Levels in AA Trees

• AA trees utilize the concept of levels to aid in balancing binary trees


- The level of a node represents the number of left links on the path to
the nullNode (sentinel node)

• All leaf nodes are at level 1

10 Level 3

5 12 Level 2

1 7 11 15 Level 1

CS350: Data Structures 4


AA Tree Invariants

• AA trees must always satisfy the following five invariants:

1) The level of a leaf node is 1

2) The level of a left child is strictly less than that of its parent

3) The level of a right child is less than or equal to that of its parent

4) The level of a right grandchild is strictly less than that of its


grandparent

5) Every node of level greater than one must have two children

CS350: Data Structures 5


Inserting Into AA Trees

• All nodes are initially inserted as leaf nodes using the standard BST
insertion algorithm (tree may require rebalancing after insert)

• Since a parent and its right child can be on the same level (rule #3),
horizontal links are possible

10 Level 3

5 12 Level 2

1 2 7 11 15 20 Level 1

CS350: Data Structures 6


Horizontal Links in AA Trees

• The five invariants of AA trees impose restrictions on horizontal


links

• If any of the invariants are violated the tree must be modified until it
once again satisfies all five invariants

• Only two cases need to be considered and corrected to maintain


the balance of an AA tree

CS350: Data Structures 7


Horizontal Links in AA Trees

• Case #1 - Left horizontal links are NOT allowed


- Violates rule #2 - the level a left child is strictly less than that of its
parent

- A skew operation will be introduced to handle this case

10 Level 3

5 12 Level 2

1 6 7 11 15 Level 1

CS350: Data Structures 8


Horizontal Links in AA Trees

• Case #2 - Two consecutive right horizontal links are NOT allowed


- Violates rule #4 - the level of a right grandchild is strictly less than
that of its grandparent

- A split operation will be introduced to handle this case

10 Level 3

5 12 Level 2

1 7 11 15 18 Level
22 1

CS350: Data Structures 9


The skew Operation

• The skew operation is a single right rotation when an insertion (or


deletion) creates a left horizontal link
- Removes the left horizontal link

- May create consecutive right horizontal links in process

P X

A B C

CS350: Data Structures 10


The skew Operation

• The skew operation is a single right rotation when an insertion (or


deletion) creates a left horizontal link
- Removes the left horizontal link

- May create consecutive right horizontal links in process

P X

A B C

CS350: Data Structures 11


The skew Operation

• The skew operation is a single right rotation when an insertion (or


deletion) creates a left horizontal link
- Removes the left horizontal link

- May create consecutive right horizontal links in process

P X P X

A B C A B C

CS350: Data Structures 12


The split Operation

• The split operation is a single left rotation when an insertion (or


deletion) creates two consecutive right horizontal links
- Removes two consecutive right horizontal links

- Increases level of middle node which may cause problems invalid


horizontal links higher in tree

X R G

A B

CS350: Data Structures 13


The split Operation

• The split operation is a single left rotation when an insertion (or


deletion) creates two consecutive right horizontal links
- Removes two consecutive right horizontal links

- Increases level of middle node which may cause problems invalid


horizontal links higher in tree

X G

A B

CS350: Data Structures 14


The split Operation

• The split operation is a single left rotation when an insertion (or


deletion) creates two consecutive right horizontal links
- Removes two consecutive right horizontal links

- Increases level of middle node which may cause problems invalid


horizontal links higher in tree

X R G X G

A B A B

CS350: Data Structures 15


Implementation of insert
1 /**
2 * Internal method to insert into a subtree.
3 * @param x the item to insert.
4 * @param t the node that roots the tree.
5 * @return the new root.
6 * @throws DuplicateItemException if x is already present.
7 */
8 private AANode<AnyType> insert( AnyType x, AANode<AnyType> t )
9 {
10 if( t == nullNode )
11
t = new AANode<AnyType>( x, nullNode, nullNode );
12
else if( [Link]( [Link] ) < 0 )
13
[Link] = insert( x, [Link] );
14
15 else if( [Link]( [Link] ) > 0 )
16 [Link] = insert( x, [Link] );
17 else
18 throw new DuplicateItemException( [Link]( ) );
19
20 t = skew( t );
21 t = split( t );
22 return t;
}

CS350: Data Structures 16


Implementation of skew

1/**
2 * Skew primitive for AA-trees.
3 * @param t the node that roots the tree.
4 * @return the new root after the rotation.
5 */
6 private static AANode<AnyType> skew( AANode<AnyType> t )
7 {
8 if( [Link] == [Link] )
9 t = rotateWithLeftChild( t );
10 return t;
11
}

CS350: Data Structures 17


Implementation of split

1/**
2 * Split primitive for AA-trees.
3 * @param t the node that roots the tree.
4 * @return the new root after the rotation.
5 */
6 private static AANode<AnyType> split( AANode<AnyType> t )
7 {
8 if( [Link] == [Link] )
9 {
10 t = rotateWithRightChild( t );
11
[Link]++;
12
}
13
return t;
14

CS350: Data Structures 18


Example of Insertion

Inserts: 6 2

Level 3

Level 2

2 6 Level 1

CS350: Data Structures 19


Example of Insertion

Inserts: 6 2

Level 3

Level 2

2 6 Level 1

CS350: Data Structures 20


Example of Insertion

Inserts: 6 2 8

Level 3

Level 2

2 6 8 Level 1

CS350: Data Structures 21


Example of Insertion

Inserts: 6 2 8

Level 3

6 Level 2

2 8 Level 1

CS350: Data Structures 22


Example of Insertion

Inserts: 6 2 8 16 10

Level 3

6 Level 2

2 8 16 Level 1
10
CS350: Data Structures 23
Example of Insertion

Inserts: 6 2 8 16 10

Level 3

6 Level 2

2 8 10 16 Level 1

CS350: Data Structures 24


Example of Insertion

Inserts: 6 2 8 16 10

Level 3

6 10 Level 2

2 8 16 Level 1

CS350: Data Structures 25


Example of Insertion

Inserts: 6 2 8 16 10 1

Level 3

6 10 Level 2

1 2 8 16 Level 1

CS350: Data Structures 26


Example of Insertion

Inserts: 6 2 8 16 10 1

Level 3

6 10 Level 2

1 2 8 16 Level 1

CS350: Data Structures 27


Deleting From AA Trees

• Perform a recursive deletion just like on other BSTs:


- To delete a leaf node (no children), simply remove the node

- To delete a node with one child, replace node with child



(in AA trees the child node will be a right child / both nodes at level 1)

- To delete an internal node, replace that node with either its successor
or predecessor

• May need to rebalance AA tree after a deletion occurs

CS350: Data Structures 28


Fixing an Unbalanced AA Tree

1) Decrease the level of a node when:


- Either of the nodes children are more than one level down

(Note that a null sentinel node is at level 0)

- A node is the right horizontal child of another node whose level was decreased

2) Skew the level of the node whose level was decremented (3 skews)
- Skew the subtree from the root, where the decremented node is the root

(may alter the root node of the subtree)

- Skew the root node’s right child

- Skew the root node’s right-right child

3) Split the level of the node whose level was decremented (2 splits)
- Split the root node of the subtree

(may alter the root node of the subtree)

- Split the root node’s right child

CS350: Data Structures 29


Excerpt From remove

1 // Rebalance tree
2 if( [Link] < [Link] - 1 || [Link] < [Link] - 1 ) // check level of children
3 {
4 if( [Link] > --[Link] ) // check level of right horizontal children
5 [Link] = [Link]; // and decrement if necessary
6 t = skew( t ); // First skew (may alter current root)
7 [Link] = skew( [Link] ); // Second skew
8 [Link] = skew( [Link] ); // Third skew
9 t = split( t ); // First split (may alter current root)
10 [Link] = split( [Link] ); // Second split
11 }

CS350: Data Structures 30


Example of Deletion

This tree can be recreated with the following sequence of inserts:


4, 10, 2, 6, 12, 3, 1, 8, 13, 11, 5, 9, 7

4 10 Level 3

2 6 8 12 Level 2

1 3 5 7 9 11 13 Level 1

CS350: Data Structures 23


31
Example of Deletion

Delete node 1
Node 2 now violates rule #5

4 10 Level 3

2 6 8 12 Level 2

1 3 5 7 9 11 13 Level 1

CS350: Data Structures 23


32
Example of Deletion

Decrement the level of node 2


Node 4 is more than one level above child

4 10 Level 3

6 8 12 Level 2

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 33


Example of Deletion

Decrement the level of nodes 4 and 10


Node 4 now has two consecutive right links
Node 10 now has left horizontal link

4 10
Level 2
6 8 12

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 34


Example of Deletion

No more level decrementing necessary


Start triple-skew, double-split process

4 10
Level 2
6 8 12

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 35


Example of Deletion

Skew node 4 (does nothing)


Next skew [Link] (node 10)

4 10
Level 2
6 8 12

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 36


Example of Deletion

After skew [Link] (node 10)


Next skew [Link] (node 10 again)

4 6 10
Level 2
8 12

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 37


Example of Deletion

After skew [Link] (node 10)


Next skew [Link] (node 10 again)

4 6 10
Level 2
8 12

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 38


Example of Deletion

After skew [Link] (node 10)


Next split node 4

4 6 8 10 12 Level 2

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 39


Example of Deletion

After split node 4 (new subtree root)


Next split node [Link] (node 8)

6 Level 3

4 8 10 12 Level 2

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 40


Example of Deletion

After split node 6


Tree is balanced

6 10 Level 3

4 8 12 Level 2

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 41


Example of Deletion

Delete node 5
Node 4 is now violates rule #5

6 10 Level 3

4 8 12 Level 2

2 3 5 7 9 11 13 Level 1

CS350: Data Structures 42


Example of Deletion

Decrement the level of node 4


Node 4 now has left horizontal link
Next skew node 4

6 10 Level 3

8 12 Level 2

2 3 4 7 9 11 13 Level 1

CS350: Data Structures 43


Example of Deletion

After skew node 4 (new subtree root)


Next skew node [Link] (node 4 again)

6 10 Level 3

8 12 Level 2

2 3 4 7 9 11 13 Level 1

CS350: Data Structures 44


Example of Deletion

After skew node [Link]


Skew node [Link] (does nothing)
Split node 2

6 10 Level 3

8 12 Level 2

2 3 4 7 9 11 13 Level 1

CS350: Data Structures 45


Example of Deletion

After split node 2 (new subtree root)


Split node [Link] (does nothing)
Tree is balanced

6 10 Level 3

3 8 12 Level 2

2 4 7 9 11 13 Level 1

CS350: Data Structures 46


Additional Slides

CS350: Data Structures 47


Implementation of Child Rotations
1 /**
2 * Rotate binary tree node with left child.
3 * For AVL trees, this is a single rotation for case 1.
4 */
5 static BinaryNode<AnyType> rotateWithLeftChild( BinaryNode<AnyType> k2 )
6 {
7 BinaryNode<AnyType> k1 = [Link];
8 [Link] = [Link];
9 [Link] = k2;
10 return k1;
11 }

1 /**
2 * Rotate binary tree node with right child.
3 * For AVL trees, this is a single rotation for case 4.
4 */
5 static BinaryNode<AnyType> rotateWithRightChild( BinaryNode<AnyType> k1 )
6 {
7 BinaryNode<AnyType> k2 = [Link];
8 [Link] = [Link];
9 [Link] = k1;
10 return k2;
11 }

CS350: Data Structures 48

You might also like