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.

Our BST & Tree Traversal Visualizer lets you step through search, insertion, removal, and four traversal orders.

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