rbtree

Documentation

Index

• type Node
  • func Rebalance(node Node) Node

Types

type Node

type Node interface {
	Parent() Node
	SetParent(Node)
	Left() Node
	SetLeft(Node)
	Right() Node
	SetRight(Node)
	IsRed() bool
	SetRed(bool)
	IsNil() bool
}

func Rebalance

func Rebalance(node Node) Node

This function rebalances and recolours trees to be valid RB trees. It needs to be called after each node that was added to the tree.

Deletions are currently not supported as this is done through the tombstone flag and from the POV of the RB-tree tombstone-nodes are just normal nodes that get rebalanced the normal way.

Throughout this file the following relationships between nodes are used: GP = grandparent, P = parent, U = uncle, S = sibling, N = node that was just added

   GP
 /   \
U     P
     / \
    S   N