Implementation of Tree
Warning: the implementation of several
methods has been left as an exercise.
The table below indicates where methods are implemented and the time
complexity of these methods. Some methods are
implemented in more than one place. When this
happens, each entry overrides the entries to its left. When an entry says "based on
iterator" or "traverse iterator" or "uses size," then the time
complexity depends on the iterator or size method.
|
|
Tree Implementation
|
Abstract
Container
|
Abstract
Tree
|
Linked
Tree
|
|
|
constructor ()
|
O(1)
|
O(1)
|
O(1)
|
|
|
|
|
|
|
| boolean
|
addFirstChild
(int index[], Object item)
|
|
uses
moveTo (index)
|
|
| boolean
|
addRoot (Object item)
|
|
exercise
|
|
| boolean
|
addRightSibling
(int index[], Object item)
|
|
uses
moveTo (index)
|
|
| void
|
clear ()
|
O(1)
|
|
O(1)
|
| Object
|
clone ()
|
|
|
exercise
|
| Collection
|
collectionView ()
|
based on iterator
|
|
|
| boolean
|
contains (Object item)
|
|
uses
get (item)
|
|
| boolean
|
equals (Object other)
|
|
exercise
|
|
| Object
|
get (Object item)
|
|
exercise
|
|
| Object
|
get (int index[])
|
|
uses
moveTo (index)
|
|
| int
|
hashCode ()
|
traverse iterator
|
|
|
| String
|
hierarchicalList ()
|
|
|
O(n)
|
| int[]
|
indexOf (Object item)
|
|
exercise
|
|
| boolean
|
isEmpty
|
uses size method
|
|
|
| Iterator
|
iterator ()
|
abstract
|
|
O(n)
|
| boolean
|
remove (Object item)
|
|
exercise
|
|
| Object
|
remove (int index[])
|
|
uses
moveTo (index)
|
|
| Object
|
set (int index[],
Object item)
|
|
uses
moveTo (index)
|
|
| int
|
size ()
|
O(1)
|
|
O(1) or O(n)
|
| Object []
|
toArray ()
|
traverse iterator
|
|
|
| String
|
toString ()
|
traverse iterator
|
|
O(n)
|
| TreeIterator
|
treeIterator ()
|
|
abstract
|
O(1)
|