Understanding Binary Search Trees, Red-Black Trees, AVL Trees, Hash Tables, and HashMaps

Binary Search Tree (BST)

Binary search tree (BST) is a tree in which all nodes follow the below mentioned properties:

1. The left sub-tree of a node has a key less than or equal to its parent node's key.
2. The right sub-tree of a node has a key greater than or equal to its parent node's key.
3. Binary search tree (BST) divides all its sub-trees into two segments: left sub-tree and right sub-tree and can be defined as left_subtree (keys) ≤ node (key) ≤ right_subtree (keys).

Red-Black Tree

A red-black tree is a binary search tree in which each node is colored red or black. The root is black. The children of a red node are black. Every path from the root to leaf has the same number of black nodes and all leaves are black.

AVL Tree

Adelson, Velski & Landis (AVL tree) is a height-balanced BST where the height of left and right subtrees differs by at most 1. This difference is called Balance Factor. To make itself balanced, an AVL tree may perform four kinds of rotations: Left rotation, Right rotation, Left-Right rotation, Right-Left rotation.

Hash Table

Hash Table is a data structure that stores data in an associative manner. Data is stored in an array format where the value has its own unique index. Access of data becomes very fast if we know the index of desired data and insertion and search operations are very fast irrespective of the size of data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or located from. Hashing is a technique to convert a range of key values into a range of indexes of an array

HashMap

An instance of HashMap (HashTable) has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets. As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur. As with all performance optimizations, it is a good idea to avoid optimizing things prematurely (i.e. without hard data on where the bottlenecks are).

Hamiltonian Graph

A connected graph G is said to be a Hamiltonian graph if there exists a cycle that contains all the vertices of G. Every cycle is a circuit but a circuit may contain multiple cycles. Such a cycle is called a Hamiltonian cycle of G.

Hamiltonian Path

Hamiltonian Path: A connected graph is said to be Hamiltonian if it contains each vertex of G exactly once. Such a path is called a Hamiltonian path.

1. Example: Hamiltonian Path - e-d-b-a-c.
2. Euler's circuit contains each edge of the graph exactly once.
3. In a Hamiltonian cycle, some edges of the graph can be skipped.