Gullu - Red Black Trees

Question 1

ADT

Answer 1

abstract data type. Represents a collection of records. Records in an ADT are position oriented rather than value oriented.

Question 2

ADT Operations

Answer 2

Create: Create an empty table
Insert: item based on search key or position
Delete
Retrieve
Traverse

Question 3

Implementations of RBT

Answer 3

Which operations are required
The frequency with which the operators will be used

Question 4

Linear Implementations of RBT

Answer 4

Array or Pointer-Based (Array vs Linked List)
Appropriateness of this implementation depends on which operations will be used and how frequently.

Question 5

Invert and Traverse in no particular order (RBT)

Answer 5

Operations needed: Insert item in list, list/traverse items there
Insert is efficient: Array based (Add at the end and increment counter) and Pointer Based (Just replace head or tail). Operations are O(1). Ex. Appending to log file.

Question 6

Traverse in Sorted Order (RBT)

Answer 6

Retrieves, inserts and deletes occur very infrequently. We can load the list and sort it when it changes. Arrays do not offer any advantage over pointer-based solutions. Only consideration is whether the size of the list is known beforehand or not.
Ex. Print catalogue for every visitor

Question 7

Traverse in sorted order and retrieve

Answer 7

Infrequent inserts and deletes. Sort after insert or delete. Array based, using binary search to retrieve by key effectively. Pointer based, so we must scan to find the middle which is inefficient.
Ex. A lookup table

Question 8

Traverse in sorted order, retrieve, insert, delete

Answer 8

Inserting and deleting: Find position of new item, insertion will cause a shift up of operation and deleting will cause a shift down. Pointer based solution is impractical cause of retrieve.

Question 9

Binary Trees

Answer 9

way to index records, if tree is balanced, we have effective traversals, inserts and deletes.

Question 10

Binary Tree useful operations

Answer 10

Find Max/Min, Find, Delete

Question 11

Rotations in an AVL Tree

Answer 11

• Minimum overhead due to low height
• For any node in the tree, the height of left and right subtrees can differ by at most one. The height of an empty tree is -1.
• After inserts/deletes, the shape is monitored to see if it conforms to AVL conditions
• Height of the tree repaired using rotation operations.

Question 12

Simple AVL implementation

Answer 12

Recursively go down to find insertion point, then go up to find height info and rebalance.

Question 13

Properties of Red-Black Trees

Answer 13

• Nodes are coloured Red or Black
• The root is black
• Children of a red node must be black
• Every path from root to null leaves has the same number of black nodes
• Null leaves are black.

Question 14

Shortest path RBT

Answer 14

only black nodes

Question 15

Longest path RBT

Answer 15

alternating black and red nodes

Question 16

Height of an RBT

Answer 16

height with n internal nodes is O(log2n)

Question 17

How many leaves in a binary tree

Answer 17

n+1 leaves if Binary tree contains N internal nodes

Question 18

General 2-3-4 tree with height h, we have bounds

Answer 18

• Minimum leaves is 2^h and max is 4^h
• N+1 leaves like merged RBT
• 2^h < n+1
• If we log both sides; h<log2(n+1)
• Height of merged RBT represents shortest possible path length by property 4. Longest possible path is twice shortest.
• For RBT having height h, we get h<2(log2(n+1))

Question 19

RBT Operations Time Complexity

Answer 19

O(log(2)n)

Question 20

Insert Strategy for RBT

Answer 20

• Use normal BST to find insert location
• Choice to insert red or black node
• New black node violates property 4, red might violate property 3
• We add red node

Question 21

Our insert strategy for RBTs

Answer 21

• Always insert red node x
• If this is the root, colour it black and we are done
• If parent P is black, we are done
• If parent is red, and uncle is black:
  
  • If relative to ground parent G, X is outside: Do a LL and recolour old G root as red and new node to black
    - If relative to ground parent G, X is inside: Do a LR and recolour as above.
• If both parents and uncle are red, the scheme won’t work and we have to recursively fix both violations.

Question 22

Comparing AVL and RBTs

Answer 22

AVL Tree height is <= 1.44log2n
RBT height is <= 2log2n
AVLs are thus faster for searching

AVL Trees typically need a pass down to find location of a new item and another pass up to rebalance the tree

RBTs appear to need the same as above, but with the requirement of recursion. We can solve this with a top down insertion.

Question 23

Deletion in RBT

Answer 23

• Red deletion is always fine
• Black deletion may cause a problem, may need to fix on the way down

Question 24

Important Points RBT

Answer 24

• AVL offers faster lookups
• AVL only needs to store balancing info of each node
• RBT only needs one extra info per node (colour)
• Insertions and deletions in RBT are faster as fewer operations are needed