Binary Tree

A binary tree is a type of tree in which each node can have at most 2 children.

Binary Search Tree

A BST is a Binary Tree, where left child <= root <= right child. Maintaining this ordering is quite easy, and provides the ability to perform quick operations on the tree.

The major issue facing BST's is keeping the tree in balance, which can be done by relaxing various balance criterion. These relaxations lead to self-balancing BST's, such as Splay Trees, Red-Black Trees, and AVL trees.


Traversals

There are 3 main traversal types when dealing with Trees.

Pre-Order

First Visit the root node, then left subtree, followed by right subtree.

In-Order

First visit the left subtree, then root node, then right subtree.

Post-Order

First visit the left subtree, then right subtree, then root node.


Trie

Tries as a special type of tree used exclusively for pattern matching. Tries are extremely helpful if you are wanting to index a particular text (Target), and be able to perform very quick searches for a particular pattern.

This is similar to preprocessing the Pattern in Boyer-Moore and KMP, we are preprocessing the Target.

Standard Trie

A standard trie follows several invariants.

  • Every node except the root is associated with a character
  • The children of each node are in alphabetical order
  • The paths from external nodes to the root are the strings contained in the set
  • No word in the trie can be a prefix of another word in the trie.

A standard trie required O(n) space, and supports searches, insertions and deletions in O(dm) time. n = total size of strings in S, m = size of string paramater in the operation, d = size of alphabet.

Compressed Trie

Similar to a Standard Trie, but all redundant chains of nodes are compressed. This removes the single character per node requirement.

Basically any node with a single child can be compressed into one node.

Suffix Tries

Suffix tries support more general pattern matching. This Trie is a Trie (generally compressed or compact form), which contains all suffixes of the Target text. This means that any substring can be found, as we can search through the tree and terminate prior to reaching an external node.


AVL Tree

The AVL tree is a special type of Binary Tree which ensures that the height of the tree is always in 'AVL Balance'.

AVL Balance is considered to be balanced, and means that for any node, the height of its children may only differ by one.

Following this criteria, it is easy to show that the height of an AVL tree is always O(logn).

When a node is inserted, a restructure must take place.. This restructure will involve at most 2 rotations, and will affect the first unbalanced node. Insertion does not trigger all the way up the tree.

When deleting a node, it is possible that an imbalance may propagate up the tree.


Splay Tree

The Splay Tree is an unusual self-balancing structure. After every access of the tree (insert, find, delete), the affected node is re-shuffled such that it becomes the root of the tree. This operation is referred to as splaying.

Due to this movement, the Splay tree is not guaranteed to be in perfect (or even near-perfect), but it works out that over a long sequence of operations, the Splay tree conforms to O(logn) depth! The benefit to this schema is that the tree also moves more-frequently accessed nodes closer to the root, and therefor is optimized for data sets containing some sort of bias. This can include items such as user databases, where certain users are likely to log in more frequently than others.

The splay operation works similar to AVL restructuring, and involves rotations to move a node to the root. As each rotation requires O(1) time, and a balanced tree would require logN operations through the depth of a tree, splaying has a total cost of O(logN).

Aside from fast searching on common items, the Splay tree is also easier to implement than most other self-balancing structures.


2-4 Tree

Insertion leads to Overflow and Split.. Push key 3 into the parent, 1,2 become left children, 4 becomes a right child.. It is possible that the parent node will then also overflow.

Deletion involves finding a key, and replacing it with its inorder successor.

2 cases transpire, Underflow with Fusion, or Underflow with Transfer.

Underflow and Fusion

We fuse together the empty node, with one of its adjacent siblings. And pull down a key from the parent to maintain balance.

It is possible for an underflow to propagate to the parent after a fusion.

Underflow and Transfer

This is basically where we move an item from an adjacent sibling of the underflow node into the parent, and then an item from the parent into the underflowing node.

This operation will never cause another underflow, and only works when the adjacent sibling contain 2 or 3 keys.

The method to chose depends on the adjacent siblings to our underflow node. Transfer is prefered, except when the adjacent node only contains one key, in which case fusion is required.


Red-Black Tree

A redblack tree is the implementation of the idea behind 2-4 trees, using a BST. This provides a simpler implementation, but requires that we keep track of a few key aspects pertaining to the relation.

Black nodes indicate the start of a node containing 1-3 keys. Following from this, the black node may have up to two red children, indicating further keys contained within this node.

Properties of Red-Black Trees

  • The root node is always black
  • Every leaf is black
  • The children of a red node are black
  • All leaves have the same black depth

Insertion

Insertion may cause a double red. If a double red occurs, either overflow has occurred, or the tree needs to be restructured.

Restructuring is easy if an overflow has not occurred, simply think about what has happened in a 2-4 tree sense.

An overflow means we must recolour the tree to maintain 2-4 balance. This involves colouring the root of this subtree red, and its two children black, creating two nodes from one. This recolour may propagate to the root. If the root becomes red, it should be coloured black, and the tree will increase by one black level.

Deletion

Deletion may cause a double black.

Restructuring - transfer equivalent, double black removed

Recolouring - Fusion equivalent, may propagate up the tree

Adjustment - Change to represent one of the above two situations.