Like the name suggests, a treap is a combination of a binary search tree and a heap. Treap nodes contain data that is organized tree-style and a priority number that is organized heap-style. The purpose of a treap is to perform operations quickly, in logarithmic time. 

University of California, Davis

A binary search tree is a specific type of tree that orders its subtrees based on the value of the node. For every node in the tree, the left sub tree must have a value less than the node (or parent) and the right sub tree must have a value greater than or equal to the node.

Binary Search Tree

AVL search trees are height balancing BSTs named after inventor Adelson, Velski & Landis. BSTs search time can go from O(logn) to O(n) if a large set of completely ordered data is inserted into the tree. This is because if data is inserted in a decreasing order, it will place many nodes to the left side of the root node. If the data is inserted in an increasing order, it will place many nodes to the right side. Either way, the BST becomes either right-heavy or left-heavy. This increases its search time and is thus undesirable. To account for this, an AVL will check its balance after each insertion to see if it is right-heavy or left-heavy and perform rotations to adjust itself accordingly. Rotations are special operations only performed to maintain the balance level of the AVL. There are four kinds of rotations the AVL may perform:
- Left rotation: The AVL rotates nodes from the right side to the left side. This rotation occurs when the tree is right-heavy. 
- Right rotation: The AVL rotates nodes from the left side to the right side. This rotation occurs when the tree is left-heavy. 
There are two additional rotations that are used when a basic rotation still results in an unbalanced tree:
- Left-right rotation: Both a left and right rotation are performed in this scenario. First, the AVL performs a rotation on the left subtree of the root node. The tree is now left heavy, and a right rotation is performed to balance it out.
- Right-left rotation: Both a right and left rotation are performed in this scenario. First, the AVL performs a rotation on the right subtree of the root node. The tree is now right heavy, and a left rotation is performed to balance it out.



AVL Search Tree

Red-Black trees are a type of Binary Search Tree that use color identifiers and rotations to balance themselves, maintaining a search time of O(logn). In a Red-Black tree, every node is assigned a color bit to identify it as red or black. There are three major rules this data structure follows:
1. Every root node is black
2. All red nodes have black children
3. The path from the root to the end of the tree contains an equal number of black nodes

Inserting nodes into a Red-Black tree may require recoloring and/or a rotation, similar to rotations found in AVL trees. The insertion algorithm and recoloring is covered below:
- If the tree is empty, insert a new node and color it black.
- Otherwise, insert a new leaf node to the end and color it red.
- If the parent node is red and its neighbor (the uncle of the inserted node) is also red, a recoloring must be done. The color of the uncle, parent, and grandparent node must be flipped.
- If the parent node is red and its neighbor (the uncle of the inserted node) is null/black (all null nodes are treated as black), then a rotation must be performed on the inserted node and the parent.
For the last step, it's possible a Left or Right rotation would be performed. This depends on which rotation would ultimately balance the tree and maintain the rules of coloring. In some cases, even after a rotation, additional rotations or recolorings will be performed until the tree is fully balanced.

Red-Black Tree

The most common operations are searching for a node, inserting a new node, and removing a node. All code snippets are provided by Bhavya Jain from GeeksForGeeks. A node may be defined like this in Python:
```python
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
```
- Searching for a node: the searching algorithm shown utilizes a recursive technique. The searching starts at the root and compares the key with the root. If it is less than the root, it continues searching to the left of the root. Otherwise, it must be greater than the root, so it continues searching to the right of the root. If the element is ever found, the search algorithm returns true. If it isn't found, it returns false. 
```python
# A utility function to search a given key in BST
def search(root,key):
     
    # Base Cases: root is null or key is present at root
    if root is None or root.val == key:
        return root
 
    # Key is greater than root's key
    if root.val < key:
        return search(root.right,key)
   
    # Key is smaller than root's key
    return search(root.left,key)
```
- Inserting a node: inserting, like searching, is recursive. We check if the root is empty, and if it is, we insert the new node as a root. This means that once we hit an available empty slot (the bottom of the tree) we can add our new node there. Otherwise we check if the root is less than the new node's key, and if it is, we go right. Otherwise, the root must be greater than the key, so we go left.
```python
def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val == key:
            return root
        elif root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root
```
- Removing a node: removal can be simple or complex depending on where the node to be removed is. If the node to be removed is a leaf (meaning it is at the bottom of the tree), it can simply be deleted. If the node to be removed has one child, the value of that child node will be copied to the parent node and then the child will be deleted. Finally, if the node to be removed has two children, the inorder successor has to be found and its value must be copied to the node, after which the inorder successor can be deleted. An inorder successor is the next node in line to take the place of the node being removed.
```python
# A utility function to do inorder traversal of BST
def inorder(root):
    if root is not None:
        inorder(root.left)
        print root.key,
        inorder(root.right)

# Given a non-empty binary
# search tree, return the node
# with minum key value
# found in that tree. Note that the
# entire tree does not need to be searched
 
 
def minValueNode(node):
    current = node
 
    # loop down to find the leftmost leaf
    while(current.left is not None):
        current = current.left
 
    return current
 
# Given a binary search tree and a key, this function
# delete the key and returns the new root
 
 
def deleteNode(root, key):
 
    # Base Case
    if root is None:
        return root
 
    # If the key to be deleted
    # is smaller than the root's
    # key then it lies in  left subtree
    if key < root.key:
        root.left = deleteNode(root.left, key)
 
    # If the kye to be delete
    # is greater than the root's key
    # then it lies in right subtree
    elif(key > root.key):
        root.right = deleteNode(root.right, key)
 
    # If key is same as root's key, then this is the node
    # to be deleted
    else:
 
        # Node with only one child or no child
        if root.left is None:
            temp = root.right
            root = None
            return temp
 
        elif root.right is None:
            temp = root.left
            root = None
            return temp
 
        # Node with two children:
        # Get the inorder successor
        # (smallest in the right subtree)
        temp = minValueNode(root.right)
 
        # Copy the inorder successor's
        # content to this node
        root.key = temp.key
 
        # Delete the inorder successor
        root.right = deleteNode(root.right, temp.key)
 
    return root
```

Binary Search Tree Operations

A splay tree is a binary search tree whose recently accessed nodes can be quickly accessed again. Splay trees work by sending nodes that are frequently accessed closer to the root of the tree, so they are quicker to access later on. This makes them good for things like caches, but this type of tree can be disadvantageous when the tree's height is linear.  

Learn Before

Related