Binary search tree

Motivation

The motivation behind using a Binary Search Tree (BST) as a data structure lies in its ability to efficiently support key-based operations, such as searching, insertion, and deletion, while maintaining a sorted order of elements.

Definition

A binary search tree (BST) is a binary tree, in which for every node, its left subtree has values less than the node’s value, and every node’s right subtree has values greater than the node’s value.

Applications

  • Map ADT

    • Stores key-value pairs

  • Set ADT

    • Stores a set of elements (keys)

Behaviors

  • Search

  • Insert

  • Remove

  • Traversal: Visit all nodes in a tree in a certain order

    • in-order: for each node: left-subtree, self, right-subtree

      • provides an ascending-ordered sequence of values

    • pre-order: for each node: self, left-subtree, right-subtree

    • post-order: for each node: left-subtree, right-subtree, self

Implementation Details

  • Algorithms that happens from top to bottom

    Easy to implement either iteratively or recursively

    • search

    • insert

  • Algorithms that happens from bottom to top

    Easy to implement recursively; Hard to implement iteratively (must use stack)

    • subtree removal (may be used in the destruction of a tree)

    • find min node or find max node (part of remove)

    • in-order traversal

    • pre-order traversal

Drawbacks and Solutions

  • Algorithm efficiency depends on the average height of the BST

  • BST may degrade a very unbalanced form or even to a linked list

  • Solutions

    • Randomize the order of insertion

    • Add a balancing mechanism

      • self-balancing tree

      • external balancing (FYI)

    • Move the most recently accessed node toward the root

      • Only optimize the search performance for a specific access pattern

      • No guarantee for the worst case

      • Splay tree

Applications of BST

  • Indexing: store a set of references in a BST and use the key as the search key

  • Tree Sort: sort a sequence of numbers by building a BST and then traversing it in-order

  • Tree Map: store a set of (key, value) pairs in a BST and use the key as the search key

  • Tree Set: store a set of elements in a BST and use the element as the search key

Important Binary Search Tree Variations

  • Self-balancing BSTs

    • AVL tree

    • Red-black tree

  • Self-adjusting BSTs (other than self-balancing)

    • Splay tree

    • Treap