Repository files navigation

Self-Balancing Binary Search Trees (AVL, Splay), with examples

Regular, non-balancing, BSTs are also included.

Available operations on trees include traversals (in-order, pre-order, post-order, level-order, both recursive and iterative), search, finding minimum and maximum values, range search (which returns a list of nodes with keys between two values), insertion, deletion, merging two trees, splitting a tree in two trees, order statistic (returning the k-th smallest element in a tree), computing rank of a node, and printing a tree.

Color flips are a way of representing arrays by using BSTs, for improved speed of operation.By using AVL trees like here (self balancing trees in general), we keep the maximum height of a tree at O(log n), so all operations on the array take at most O(log n) time.