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

A red-black tree is a self-balancing binary search tree where each node has a color attribute (red or black). This coloring scheme and a set of balancing rules ensure that the tree remains balanced, maintaining a search time complexity of $$O(\log n)$$.

### Properties of a Red-Black Tree
A valid red-black tree must satisfy the following major rules:
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.

Red-Black Tree

A binary search tree stores smaller values in the left subtree and larger values in the right subtree. The example below shows the three standard operations: lookup, insertion, and deletion. The deletion routine covers the three usual cases: no children, one child, or two children.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def contains(node, target):
    # Walk downward until the value is found or the branch ends.
    while node is not None:
        if target == node.value:
            return True
        if target < node.value:
            node = node.left
        else:
            node = node.right
    return False


def insert(node, value):
    # Create a new leaf when the search path reaches an empty spot.
    if node is None:
        return TreeNode(value)

    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)

    return node


def leftmost(node):
    # The minimum value in a subtree is stored at the far left.
    current = node
    while current is not None and current.left is not None:
        current = current.left
    return current


def remove(node, value):
    # Stop when the subtree is empty.
    if node is None:
        return None

    if value < node.value:
        node.left = remove(node.left, value)
    elif value > node.value:
        node.right = remove(node.right, value)
    else:
        # Case 1: no left child
        if node.left is None:
            return node.right

        # Case 2: no right child
        if node.right is None:
            return node.left

        # Case 3: two children, replace with the in-order successor.
        successor = leftmost(node.right)
        node.value = successor.value
        node.right = remove(node.right, successor.value)

    return node


def inorder(node):
    # Useful for checking that the tree still remains sorted.
    if node is not None:
        inorder(node.left)
        print(node.value, end=" ")
        inorder(node.right)

Binary Search Tree Core Operations in Python

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.  

Splay Tree

A treap is a data structure that combines the properties of a binary search tree and a heap. Each node in a treap contains a data key (organized according to the binary search tree property) and a priority value (organized according to the heap property). This structure allows operations to be performed in $$O(\log n)$$ time.

Treap

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.

Boston University

A tree is an abstract data structure that represents a hierarchical tree. A tree contains a root which is connected to subtrees through linked nodes. The tree data structure is inherently recursive, since a node's subtree is also a tree in and of itself.
A node that has a subtree is the "parent" node of the subtree. The nodes within the subtree of the parent node are called "child" nodes. Child nodes that have the same parent are known as "sibling" nodes.

There are many types of tree data structures. A few of them include:
- Binary Tree (Binary Search Tree)
     1. AVL Tree
     2. Red-Black Tree
     3. Splay Tree
     4. Treap
- B-Tree
- N-ary Tree

Tree

Binary Tree Data Structure 

A B - tree is a self balancing search tree. They are used to lower the amount of times that a disk is accessed - which is how the data from the tree is read. As a result, the number of keys (or values) in a given node of the tree is maximized to lower the height of a B - Tree.

B - Trees

A N - Ary Tree is a tree data structure where every node does not have more than N children. For example, every node in a 3 - Ary tree has either 0, 1, 2, or 3 children nodes. 

N - Ary Tree

A complete binary tree must have each level be completely occupied except the last level and have no gaps in the last level (so each node in the last level is as far to the left as it can be). 

Complete Binary Tree

https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html#:~:text=A%20full%20binary%20tree%20(sometimes,as%20far%20left%20as%20possible.

Full and Complete Binary Tree

A full binary tree is a binary tree where each node must have either zero or two children. In effect, each node has two children except for the leaf nodes.

Full Binary Tree

A k-d tree (k-dimensional tree) is a space-partitioning binary tree data structure used for organizing points in a k-dimensional space. It is particularly useful for optimizing nearest neighbor searches, significantly improving the prediction time complexity of algorithms like k-nearest neighbors (k-NN) by continuously dividing the vector space using a divide-and-conquer approach. Each internal node represents a vector sub-space, recording a division along the $$r^{th}$$ dimension with a fixed threshold value and containing pointers to its two child nodes. To build the tree, a common approach is to compute the median and variance for each feature, select the feature with the largest variance, and recursively divide the dataset into two subsets based on that feature's median. For nearest neighbor retrieval, the algorithm traverses the tree to find the appropriate branch, drastically reducing the number of distance comparisons needed.

Learn Before

Related

Learn After

Learn After

Related