How TreeSet Works Internally In Java : Tree theory: interview questions
What is treeset?
Treeset is a java set implementation which contains unique set of elements with total ordering of data.Each and every element input to a tree-set are comparable or by some other means like custom java comparator to define the ordering property for the elements.
Lets define a tree structure?
Tree terminologies:
TreeSet
Treeset is a java set implementation which contains unique set of elements with total ordering of data.Each and every element input to a tree-set are comparable or by some other means like custom java comparator to define the ordering property for the elements.
Lets define a tree structure?
A tree is basically a nonlinear and hierarchical data structure consisting of nodes and edges.Every tree has a root node , 0 or more number of intermediary child nodes and 0 or more certain number of leaf nodes.Tree must have no cycles and only one root node.Based on the maximum number of child nodes a tree can have, the tree can be classified as unary, binary, ternary etc.
Tree terminologies:
Root
|
The top node in a tree.
|
Child
|
A node directly connected to another node when moving away from the Root.
|
Parent
|
The converse notion of a child.
|
Siblings
|
A group of nodes with the same parent.
|
Descendant
|
A node reachable by repeated proceeding from parent to child.
|
Ancestor
|
A node reachable by repeated proceeding from child to parent.
|
Leaf
|
A node with no children.
|
Internal node
|
A node with at least one child.
|
Degree
|
The number of subtrees of a node.
|
Edge
|
The connection between one node and another.
|
Path
|
A sequence of nodes and edges connecting a node with a descendant.
|
Level
|
The level of a node is defined by 1 + (the number of connections between the node and the root).
|
Height of node
|
The height of a node is the number of edges on the longest path between that node and a leaf.
|
Height of tree
|
The height of a tree is the height of its root node.
|
Depth
|
The depth of a node is the number of edges from the tree's root node to the node.
|
Forest
|
A forest is a set of n ≥ 0 disjoint trees.
|
TreeSet
TreeSet provides an implementation of the Set interface that uses a tree for storage. Objects are stored in sorted, ascending order.
Access and retrieval times are quite fast, which makes TreeSet an excellent choice when storing large amounts of sorted information that must be found quickly.
The TreeSet class supports four constructors. The first form constructs an empty tree set that will be sorted in ascending order according to the natural order of its elements:
- TreeSet( ) : The second form builds a tree set that contains the elements of c.
- TreeSet(Collection c) : The third form constructs an empty tree set that will be sorted according to the comparator specified by comp.
- TreeSet(Comparator comp): The fourth form builds a tree set that contains the elements of ss:
- TreeSet(SortedSet ss)
Apart from the methods inherited from its parent classes, TreeSet defines the following methods:
1.void add(Object o):Adds the specified element to this set if it is not already present.2.boolean addAll(Collection c):Adds all of the elements in the specified collection to this set.3.void clear():Removes all of the elements from this set.4.Object clone():Returns a shallow copy of this TreeSet instance.5.Comparator comparator():Returns the comparator used to order this sorted set, or null if this tree set uses its elements natural ordering.6.boolean contains(Object o):Returns true if this set contains the specified element.7.Object first():Returns the first (lowest) element currently in this sorted set.8.SortedSet headSet(Object toElement):Returns a view of the portion of this set whose elements are strictly less than toElement.9.boolean isEmpty():Returns true if this set contains no elements.10.Iterator iterator():Returns an iterator over the elements in this set.11.Object last():Returns the last (highest) element currently in this sorted set.12.boolean remove(Object o):Removes the specified element from this set if it is present.13.int size():Returns the number of elements in this set (its cardinality).14.SortedSet subSet(Object fromElement, Object toElement):Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.15.SortedSet tailSet(Object fromElement):Returns a view of the portion of this set whose elements are greater than or equal to fromElement.