com.alexprut.algo.datastructures

Class RedBlackTree

java.lang.Object

com.alexprut.algo.datastructures.RedBlackTree

public class RedBlackTree
extends java.lang.Object

A red-black tree is a binary tree that satisfies the following red-black properties: 1) Every node is either red or black 2) The root is black 3) Every leaf (NULL) is black 4) If a node is red, then both its children are black 5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	RedBlackTree.Node

Method Summary

Modifier and Type	Method and Description
int	blackHeight() Number of black nodes on any simple path from, but not including, a node x down to a leaf
boolean	delete(int value) Time complexity: O(logn)
void	insert(int value) Time complexity: O(logn)
void	insertFixup(RedBlackTree.Node x) Time complexity: O(logn)
boolean	search(int value) Time complexity: O(logn)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

insert

public void insert(int value)

Time complexity: O(logn)

insertFixup

public void insertFixup(RedBlackTree.Node x)

Time complexity: O(logn)

search

public boolean search(int value)

Time complexity: O(logn)

delete

public boolean delete(int value)

Time complexity: O(logn)

blackHeight

public int blackHeight()

Number of black nodes on any simple path from, but not including, a node x down to a leaf