redblacktree

Documentation

Index

• type Color
• type RBTree
  • func (T *RBTree) Insert(x *RBTreeNode)
• type RBTreeNode

Types

type Color

type Color int8

const (
	RED Color = iota
	BLACK
)

type RBTree

type RBTree struct {
	Root *RBTreeNode
}

A Red-Black tree is a binary search tree which has the following red-black properties:

1. Every node is either red or black.

2. Every leaf(nil) is black.

3. If a node is red, then both its children are black.(Which implies that on a path from the root to a leaf, red nodes must not be adjacent. However, any number of black nodes may appear in a sequence.)

4. Every simple path from a node to a descendant leaf contains the same number of black nodes.

   Examples: A basic red-balck tree 11B 2R 14B 1B 7B 15R 5R 8R

func (*RBTree) Insert

func (T *RBTree) Insert(x *RBTreeNode)

type RBTreeNode

type RBTreeNode struct {
	Key                 int64
	Color               Color
	Value               interface{}
	Left, Right, Parent *RBTreeNode
}