Binary Search Trees - Red Black Trees Flashcards
key properties of red black BSTs
no node has 2 red links connected to it
every path from root to null link has the same number of black links
red links lean left
root is always black
what colour is the root node always
black
can a red node have a red child
no
can a red node have a red parent
no
if a node is red then what colour will both its children be
black
the red black BST is only balanced when we consider what colour links
black
guaranteed upper bound for methods in red black bst
log n
why is log n the guaranteed cost of operations in red black bst
making sure we maintain balance means that all the operations will have an upper bound of the height of the tree
are leaf nodes counted as red or black nodes
black
to what direction do red links lean
left
what are the four members of the node class in a red black tree
key
value
noe left and right
boolean colour
what does the left rotation method do
orient a right leaning red link to the left
what does the right rotation method do
orient a left leaning link to the right temporarily
what does the recolour method do
changes colour of node
how to insert into a tree with exactly one node (left side)
add node with a red link
