Package dsa.lab08.solutions

Class AVLTree<Key extends Comparable<Key>,Value>

java.lang.Object

dsa.lab07.solutions.BinarySearchTree<Key,Value>

dsa.lab08.solutions.AVLTree<Key,Value>

Type Parameters:

Key - the key type

Value - the value type

All Implemented Interfaces:

Container<MapItem<Key,Value>>, Map<Key,Value>, OrderedMap<Key,Value>, Iterable<MapItem<Key,Value>>

public class AVLTree<Key extends Comparable<Key>,Value>
extends BinarySearchTree<Key,Value>

An AVL tree.

Nested Class Summary

Nested classes/interfaces inherited from class dsa.lab07.solutions.BinarySearchTree

BinarySearchTree.ItemIterator<Key extends Comparable<Key>,Value>, BinarySearchTree.Node<Key extends Comparable<Key>,Value>

Field Summary

Fields inherited from class dsa.lab07.solutions.BinarySearchTree

root, size

Constructor Summary

Constructors

Constructor	Description
AVLTree()	Construct an empty AVL tree.
AVLTree(MapItem<Key,Value>... items)	Construct an AVL tree containing the given items.
AVLTree(Iterable<MapItem<Key,Value>> items)	Construct an AVL tree containing the given items.

Method Summary

Modifier and Type	Method	Description
boolean	_isAVLConditionSatisfied()
boolean	_isHeightCacheCorrect()
void	insert(MapItem<Key,Value> item)	Insert the given item.
MapItem<Key,Value>	remove(Key key)	Remove and return the item with the given key.

Methods inherited from class dsa.lab07.solutions.BinarySearchTree

find, findNode, items, max, min, next, previous, reversed, size, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface dsa.lab02.base.Container

contains, isEmpty, iterator

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface dsa.lab04.base.Map

containsKey, containsValue, get, insert, values

Methods inherited from interface dsa.lab05.base.OrderedMap

keys, reversedKeys

Constructor Details

AVLTree

public AVLTree()

Construct an empty AVL tree.

AVLTree

public AVLTree(Iterable<MapItem<Key,Value>> items)

Construct an AVL tree containing the given items.

Parameters:

items - the items

AVLTree

@SafeVarargs
public AVLTree(MapItem<Key,Value>... items)

Construct an AVL tree containing the given items.

Parameters:

items - the items

Method Details

insert

public void insert(MapItem<Key,Value> item)

Description copied from interface: Map

Insert the given item.

If there's already an item with the same key, that item is replaced with this one.

This means that if the key was not already contained, the size is incremented, otherwise it isn't.

Specified by:

insert in interface Map<Key extends Comparable<Key>,Value>

Overrides:

insert in class BinarySearchTree<Key extends Comparable<Key>,Value>

Parameters:

item - the item

remove

public MapItem<Key,Value> remove(Key key)
                          throws NoSuchElementException

Description copied from interface: Map

Remove and return the item with the given key.

Decrements the size (assuming the item was actually in the map).

Specified by:

remove in interface Map<Key extends Comparable<Key>,Value>

Overrides:

remove in class BinarySearchTree<Key extends Comparable<Key>,Value>

Parameters:

key - the item's key

Returns:

the item

Throws:

NoSuchElementException - if key is not contained

_isHeightCacheCorrect

public boolean _isHeightCacheCorrect()

_isAVLConditionSatisfied

public boolean _isAVLConditionSatisfied()