Data Structures

Usually, sorting and searching algorithms have been characterized by the number of comparison operations that must be performed using order notation (Big O).

Tree

Binary Tree
A tree where each node has at most two children.


Binary Search Tree
A binary tree where the right child is greater than the parent and the left child is less than the parent. (sometimes called ordered or sorted binary trees)
The worst-case time of build_binary_tree is O(n^2)—if you feed it a sorted list of values, it chains them into a linked list with no left subtrees. For example, build_binary_tree([1, 2, 3, 4, 5]) yields the tree (1 (2 (3 (4 (5)))))

Binary Search Tree -
A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.  The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc

Self balancing Binary Tree
A self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.

One advantage of self-balancing BSTs is that they allow fast (indeed, asymptotically optimal) enumeration of the items in key order, which hash tables do not provide

One disadvantage is that their lookup algorithms get more complicated when there may be multiple items with the same key.

Self-balancing BSTs have better worst-case lookup performance than hash tables (O(log n) compared to O(n)), but have worse average-case performance (O(log n) compared to O(1)).

Sorting Time for Self Balancing Binary Search Tree = O(nlogn)

For average-case performance, however, self-balanced BSTs may be less efficient than other solutions.
Binary tree sort, in particular, is likely to be slower than merge sort, quicksort, or heapsort, because of the tree-balancing overhead as well as cache access patterns


AVL tree is a self-balancing binary search tree.

B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children

        Average Worst case
Space O(n)        O(n)
Search O(log n) O(log n)
Insert O(log n) O(log n)
Delete O(log n) O(log n)

Heap

A heap is a specialized tree-based Abstract data type that satisfies the heap property. If A is a parent node of B then the key of node A is ordered with respect to the key of node B with the same ordering applying across the heap. Heaps can be classified further as either a "max heap" or a "min heap". In

Java Data Structures

Map

HashMap
TreeMap - A Red-Black tree based NavigableMap implementation

LinkedHashMap - Maintains ordering

Hashtable - Synchronised
WeakHashMap - Hash table based implementation of the Map interface, with weak keys. An entry in a WeakHashMap will automatically be removed when its key is no longer in ordinary use

Set

HashSet - This class implements the Set interface, backed by a hash table (actually a HashMap instance).
TreeSet - A NavigableSet implementation based on a TreeMap
LinkedHashSet - This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries.


List

ArrayList
LinkedList
Vector - synchronised


Red-Black tree
A red–black tree is a binary search tree with an extra bit of data per node, its color, which can be either red or black