com.alexprut.algo.datastructures

Class BinarySearchTree

java.lang.Object

com.alexprut.algo.datastructures.BinarySearchTree

public class BinarySearchTree
extends java.lang.Object

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BinarySearchTree.BinaryNode

Constructor Summary

Constructors

Constructor and Description
BinarySearchTree()

Method Summary

Modifier and Type	Method and Description
boolean	contains(int value) Time complexity: O(logn) if the tree is balanced, O(n) in the worst case
void	insert(int value) Time complexity: O(logn) if the tree is balanced, O(n) in the worst case
BinarySearchTree.BinaryNode	maximum() Time complexity: O(logn) if the tree is balanced, O(n) in the worst case
BinarySearchTree.BinaryNode	minimum() Time complexity: O(logn) if the tree is balanced, O(n) in the worst case
void	remove(BinarySearchTree.BinaryNode node) Time complexity: O(logn) if the tree is balanced, O(n) in the worst case
BinarySearchTree.BinaryNode	search(int value) Time complexity: O(logn) if the tree is balanced, O(n) in the worst case
int	size() Time complexity: Θ(1)

Methods inherited from class java.lang.Object

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

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Method Detail

insert

public void insert(int value)

Time complexity: O(logn) if the tree is balanced, O(n) in the worst case

search

public BinarySearchTree.BinaryNode search(int value)

Time complexity: O(logn) if the tree is balanced, O(n) in the worst case

remove

public void remove(BinarySearchTree.BinaryNode node)

Time complexity: O(logn) if the tree is balanced, O(n) in the worst case

contains

public boolean contains(int value)

Time complexity: O(logn) if the tree is balanced, O(n) in the worst case

size

public int size()

Time complexity: Θ(1)

minimum

public BinarySearchTree.BinaryNode minimum()

Time complexity: O(logn) if the tree is balanced, O(n) in the worst case

maximum

public BinarySearchTree.BinaryNode maximum()

Time complexity: O(logn) if the tree is balanced, O(n) in the worst case