The study of mathematic structures called graphs. Part of discrete mathematics (study of fundamentally discrete structures, non continuous). Graphs represent a set of objects, where some objects are connected by links. Objects are verticies and links are edges.
Edges may be directed or undirected (graph of people who met vs. graph of people who know of other people).
Definition: graph G = (V,E), a set of V vertices or nodes, with a set of E edges, where any given edge is an unordered 2-element subset of V (or a pair of verticies).
Adjancency: Two eges of a graph are adjacent if they share a common vertex.
Node based BST that automatically keeps its height small, on insert/delete. Desirable since trees take operation time proportional to their height (optimally log(n)).
Self-balancing binary search tree. Balance is preserved by "painting" each node red or black (extra bit for each node). These nodes must satisfy properties that collectively constrain how unbalanced a tree can become in worst case.
These imply an important property: The path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.
Learned this in an interview at startup Drop Loyalty! Specific application of a binary tree used to represent mathematical expressions. The nodes are all binary or unary operations except for the leaves which are values that are operated on. The whole tree represents and expression, or a result if there are no variable values in the expression tree.
Scheme like representation of the expression tree: (+ (* (+ a b) c) 7) using in-order traversal.