# Exercise 14.3.6

Show how to maintain a dynamic set $Q$ of numbers that supports the operation MIN-GAP, which gives the magnitude of the difference of the two closes numbers in $Q$. For example, if $Q = \{ 1, 5, 9, 15, 18, 22 \}$, then MIN-GAP(Q) returns $18 - 15 = 3$, since $15$ and $18$ are the two closest numbers in $Q$. Make the operations INSERT, DELETE, SEARCH and MIN-GAP as efficient as possible, and analyze their running times.

This should be formulaic.

We store the following extra attributes in each node:

• minimum of the subtree rooted at the node
• maximum of the subtree rooted at the node
• gap (minimal one) for the subtree root at the node

We can calculate the extra attributes for each node in the following way:

• The minimum is the left subtree's minimum if it exist, or the key of the node if it doesn't.
• The maximum is the right subtree's maximum if it exists, or the key of the node if it doesn't.
• There are four candidates for the min gap, whichever is smallest is fine.
1. The left subtree's min gap, if there is a left node
2. The right subtree's min gap, if there is a right node
3. node.key - node.left.maximum, if there is a left node
4. node.right.minimum - node.key, if there is a right node

To maintain invariants, we need to recalculate the extras when:

• We do a rotation
• We insert a node, starting with the inserted node
• We delete a node, starting with the lowest node we've moved

This results in the code below.

### Python code

from enum import Enum
from collections import deque

class Color(Enum):
RED = 1
BLACK = 2

NIL_KEY = object()

def other(direction):
if direction == 'left':
return 'right'
elif direction == 'right':
return 'left'
else:
assert(False)

class Extra:
def __init__(self, minimum, maximum, gap):
self.minimum = minimum
self.maximum = maximum
self.gap = gap

class Node:
def __init__(self, color, key, parent, left, right, extra, tree):
self.color = color
self.key = key
self.parent = parent
self.left = left
self.right = right
self.extra = extra
self.tree = tree

def sexp(self):
if self.isNil():
return 'NIL'

color = 'R' if self.color == Color.RED else 'B'

return f"{color}({self.key}, {self.left}, {self.right})"

__str__ = sexp

def black_height(self):
node = self
height = 0

while node is not nil:
if node.color == Color.BLACK:
height += 1
node = node.parent

return height

def isRed(self):
return self.color == Color.RED

def isBlack(self):
return self.color == Color.BLACK

def isNil(self):
return self.key is NIL_KEY

def isNotNil(self):
return not self.isNil()

def __bool__(self):
return self.isNotNil()

def child(self, direction):
if direction == 'left':
return self.left
elif direction == 'right':
return self.right
else:
assert(False)

def set_child(self, direction, child):
if direction == 'left':
self.left = child
elif direction == 'right':
self.right = child
else:
assert(False)

__getitem__ = child
__setitem__ = set_child

def other(self, direction):
return self.child(other(direction))

def rotate(self, direction):
child = self.other(direction)
self[other(direction)] = child[direction]

if child[direction]:
child[direction].parent = self

child.parent = self.parent

if not self.parent:
self.tree.root = child
elif self is self.parent[direction]:
self.parent[direction] = child
else:
self.parent[other(direction)] = child

child[direction] = self
self.parent = child

self.recalculate()
child.recalculate()

def left_rotate(self):
self.rotate('left')

def right_rotate(self):
self.rotate('right')

def transplant(self, other):
if not self.parent:
self.tree.root = other
elif self is self.parent.left:
self.parent.left = other
else:
self.parent.right = other
other.parent = self.parent

def set(self, parent=None, left=None, right=None, color=None):
if color:
self.color = color
if left is not None:
self.left = left
if right is not None:
self.right = right
if parent is not None:
self.parent = parent

def minimum(self):
node = self

while node.left:
node = node.left

return node

def maximum(self):
node = self

while node.right:
node = node.right

return node

def recalculate(self):
self.extra.minimum = self.left.extra.minimum if self.left else self.key
self.extra.maximum = self.right.extra.maximum if self.right else self.key

self.extra.gap = min(n for n in [
self.left.extra.gap if self.left else None,
self.right.extra.gap if self.right else None,
self.key - self.left.extra.maximum if self.left else None,
self.right.extra.minimum - self.key if self.right else None,
float('inf')
] if n is not None)

nil = Node(Color.BLACK, NIL_KEY, None, None, None, None, None)
nil.parent = nil
nil.left = nil
nil.right = nil

class MinGapTree:
def __init__(self):
self.root = nil

def __str__(self):
return self.root.sexp()

def min_gap(self):
return self.root.extra.gap

def search(self, key):
node = self.root

while node:
if node.key == key:
return node
elif key < node.key:
node = node.left
else:
node = node.right

return None

def nodes(self):
items = deque()

if self.root:
items.append(self.root)

while items:
node = items.popleft()

yield node

if node.left:
items.append(node.left)

if node.right:
items.append(node.right)

def insert(self, key):
extra = Extra(minimum=float('inf'), maximum=float('-inf'), gap=float('inf'))
new = Node(Color.RED, key, None, None, None, extra, self)
parent = nil
node = self.root
while node:
parent = node
if new.key < node.key:
node = node.left
else:
node = node.right

new.parent = parent

if not parent:
self.root = new
elif new.key < parent.key:
parent.left = new
else:
parent.right = new

new.set(left=nil, right=nil, color=Color.RED)

self.extras_fixup(new)

self.insert_fixup(new)

def insert_fixup(self, node):
while node.parent.isRed():
if node.parent is node.parent.parent.left:
direction = 'left'
else:
direction = 'right'

if direction == 'left' or direction == 'right':
uncle = node.parent.parent[other(direction)]
if uncle.isRed():
node.parent.color = Color.BLACK
uncle.color = Color.BLACK
node.parent.parent.color = Color.RED
node = node.parent.parent
else:
if node is node.parent[other(direction)]:
node = node.parent
node.rotate(direction)
node.parent.color = Color.BLACK
node.parent.parent.color = Color.RED
node.parent.parent.rotate(other(direction))

self.root.color = Color.BLACK

def delete(self, key):
deleted = self.search(key)
y = deleted
y_original_color = y.color

if not deleted.left:
extra_black = deleted.right
deleted.transplant(deleted.right)
self.extras_fixup(deleted)
elif not deleted.right:
extra_black = deleted.left
deleted.transplant(deleted.left)
self.extras_fixup(deleted)
else:
y = deleted.right.minimum()
y_original_color = y.color
extra_black = y.right
to_fix = y

if y.parent is deleted:
extra_black.parent = y
else:
to_fix = y.parent
y.transplant(y.right)
y.right = deleted.right
y.right.parent = y

deleted.transplant(y)
y.left = deleted.left
y.left.parent = y
y.color = deleted.color

self.extras_fixup(to_fix)

if y_original_color == Color.BLACK:
self.delete_fixup(extra_black)

def delete_fixup(self, node):
while node is not self.root and node.isBlack():
if node is node.parent.left:
direction = 'left'
else:
direction = 'right'

sibling = node.parent[other(direction)]

if sibling.isRed():
sibling.color = Color.BLACK
node.parent.color = Color.RED
node.parent.rotate(direction)
sibling = node.parent[other(direction)]

if sibling.left.isBlack() and sibling.right.isBlack():
sibling.color = Color.RED
node = node.parent
else:
if sibling[other(direction)].isBlack():
sibling[direction].color = Color.BLACK
sibling.color = Color.RED
sibling.rotate(other(direction))
sibling = node.parent[other(direction)]

sibling.color = node.parent.color
node.parent.color = Color.BLACK
sibling[other(direction)].color = Color.BLACK
sibling.parent.rotate(direction)
node = self.root

node.color = Color.BLACK

def extras_fixup(self, node):
while node:
node.recalculate()
node = node.parent