Java Interview Guide: How to Build Confidence With a Solid Understanding of Core Java Principles pdfdrive com

Binary Search Tree
A binary search tree (BST) is a data structure that sorts nodes in a hierarchical
tree. A red-black tree is a BST implementation that colors each node according
to its location. The color of adjacent nodes can determine whether or not a tree
is balanced. An unbalanced tree degrades to 
O(n)
time on lookups, so a
balancing operation is used after inserting or removing nodes to guarantee
lookups in 
O(log n)
time.
TreeMap
is a red-black tree implementation that uses entry nodes to store its
values. An 
Entry
object contains a key, a value, a color, and a reference to its
parent entry, left entry, and right entry. A 
TreeMap
stores its entries according
to the natural ordering of their keys or by a sorting strategy provided
by a 
Comparator
. A naturally sorted tree requires that keys correctly
implement the 
compareTo()
and 
equals()
methods in the 
Comparable
interface. A 
TreeMap
iterates through its entries in sorted order. 
TreeMap
is not thread-safe, but it can be decorated by the
Collections#synchronizedSortedMap() 
method.

---

Heap
A heap is an unsorted data structure that organizes nodes in a hierarchical tree.
In a 
max-heap
, the values of a parent node are always greater than the values
of its child nodes. In a 
min-heap
, the values of a parent node are always less than
the values of its child nodes.
A heap is a maximally efficient implementation of a priority queue. A priority
queue serves elements according to their priority and falls back to a FIFO policy
for identical priorities. The 
PriorityQueue
class uses an object array to store
its values. Although heaps are visually represented as a tree, they can
be compactly stored inside of an array and nodes can be located by index
arithmetic. 
PriorityQueue
is not thread-safe,
but 
PriorityBlockingQueue
is a thread-safe alternative.

---

Set
A 
Set
is a data structure that holds a collection of unique values. Sets often
delegate functionality to maps because the keys in a map are already unique.
HashSet
utilizes a 
HashMap
, which does not maintain the insertion order
of its elements. 
LinkedHashSet
utilizes a 
LinkedHashMap
,
which maintains insertion order by way of an auxiliary 
LinkedList
.
TreeSet
utilizes a 
TreeMap
, which maintains the natural ordering of its
elements. None of these classes are thread-safe, but the
Collections#newSetFromMap()
method can create a set out
of a 
ConcurrentHashMap
.

---