redblacktree

package
Version: v0.0.0-...-241115c Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 25, 2021 License: MIT Imports: 1 Imported by: 0

Documentation

Overview

Package redblacktree is an implementation for left leaning red black tree data structure in go language.

Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node has a color either red or black. Root of tree is always black. There are no two adjacent red nodes (A red node cannot have a red parent or red child). Every path from a node (including root) to any of its descendant NULL node has the same number of black nodes.

Why Red-Black Trees

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of a Red-Black tree is always O(Logn) where n is the number of nodes in the tree.

The main problem with BST deletion (Hibbard Deletion) is that It is not symmetric. After many insertion and deletion BST become less balance. Researchers proved that after sufficiently long number of random insert and delete height of the tree becomes sqrt(n) .So now every operation (search, insert, delete) will take sqrt(n) time which is not good compare to O(logn) .

This is very long standing(around 50 years) open problem to efficient symmetric delete for BST. for guaranteed balanced tree, we have to use RedBlack Tree etc.

Properties

- No Node has two red links connected to it.
- Every path from root to null link has the same number of black links.
- Red links lean left.

Index

Constants

View Source
const (
	RED   = 0
	BLACK = 1
)

Variables

This section is empty.

Functions

This section is empty.

Types

type Node

type Node struct {
	Data   int
	Color  int
	Parent *Node
	Left   *Node
	Right  *Node
}

Node struct contains actual data, color and address to left, right and parent node

func NewNode

func NewNode(data, color int) *Node

NewNode creates a new Node with default integer data

type RBTree

type RBTree struct {
	Root *Node
	Size int
}

Tree struct contains the pointer to root node and total number of nodes.

func NewRBTree

func NewRBTree() *RBTree

NewRBTree creates an empty Red Black Tree

func (*RBTree) Find

func (t *RBTree) Find(data int) bool

Find returns true if integer is present in RBTree, else false.

func (*RBTree) FindMax

func (t *RBTree) FindMax() (int, error)

FindMax returns the max element from the dataset

func (*RBTree) FindMin

func (t *RBTree) FindMin() (int, error)

FindMin returns the max element from the dataset

func (*RBTree) Insert

func (tree *RBTree) Insert(data int)

Insert inserts new node into the red black tree

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL