Binary Search Trees

Binary Search Trees (BST)

  • A binary search tree (BST) is a special type of binary tree.

    • Key Characteristics:

    • Each node contains a unique key value and potentially additional data.

    • For any node n in the tree:

      • All keys in n's left subtree are less than the key in n.

      • All keys in n's right subtree are greater than the key in n.

    • Duplicate Keys: If duplicate keys are allowed, nodes with values equal to the key of node n can be placed either in the left or right subtree, but not both. In these notes, duplicates are assumed not to be allowed.

Examples of Binary Search Trees

  • Examples of BSTs, where each node stores an integer key:

    • Example Trees:

    • Tree structure to visualize valid BSTs.

Invalid BSTs

  • Non-BST Examples:

    • Example 1: Left node with key 5 not greater than root node 6.

    • Example 2: Left node with key 6 not greater than node 7.

Multiple Representations of the Same Set of Keys

  • Different BSTs: More than one BST can represent the same set of keys. For example, two distinct BST structures can store identical sets of integer keys while maintaining all characteristics of a BST.

Importance of Binary Search Trees

  • Efficiency: Binary search trees provide efficient implementations for the following operations:

    • Insert a key value: Place a new key in the correct position in the tree.

    • Determine existence of a key value: Check if a key is present in the tree.

    • Remove a key value: Delete a specific key from the tree.

    • Print key values in sorted order: Facilitate ordered traversal of keys.

Implementing BSTs

  • Classes Used:

    • Two classes are required to implement a binary search tree:

    • One for individual tree nodes.

    • One for the binary search tree itself.

Representing Binary Trees

  • Node Structure:

    • A binary tree can be represented using linked nodes:

    • Each node contains:

      • A value (E element)

      • Two links (TreeNode<E> left, TreeNode<E> right) referencing the left and right children, respectively.

    • Example of a node class in Java:
      java class TreeNode<E> { E element; TreeNode<E> left; TreeNode<E> right; public TreeNode(E o) { element = o; } }

    • Root Node: The variable root refers to the root node of the tree; if the tree is empty, root is null.

Creating Nodes in a Tree

  • Node Creation Example:

    • Creation of the first three nodes in a BST:
      java // Create the root node TreeNode<Integer> root = new TreeNode<>(60); // Create the left child node root.left = new TreeNode<>(55); // Create the right child node root.right = new TreeNode<>(100);

Searching for an Element in a BST

  • The process begins at the root and proceeds to scan downwards until a match is found or a leaf node is reached.

  • Algorithm Steps:

    • Let current refer to the root:

    • While current is not null or the element matches current.element:

      • If the element is less than current.element, assign current.left to current.

      • If the element is greater than current.element, assign current.right to current.

      • If the element equals current.element, return true.

      • If current is null, the element is not in the tree.

Inserting an Element into a BST

  • Process: To insert an element, locate the appropriate position based on the key.

  • Key Idea: Find the correct parent node for the new element.

  • Algorithm:

    • If the tree is empty, create a root node with the new element.

    • Otherwise, locate the parent node for the new element:

    • If the new element is less than the parent element, the new element is a left child.

    • If the new element is greater, it becomes the right child.

  • Java Code Example:
    java if (root == null) root = new TreeNode(element); else { // Locate the parent node current = root; while (current != null) { if (element < current.element) { parent = current; current = current.left; } else if (element > current.element) { parent = current; current = current.right; } else return false; // Duplicate not inserted } // Create new node and attach to parent if (element < parent.element) parent.left = new TreeNode(element); else parent.right = new TreeNode(element); return true; // Element inserted }

Traversing and Visualizing Insertions

  • Visual representation of a tree along with insertion steps.

Tree Traversal Methods

  • Definition: Tree traversal involves visiting each node exactly once.

  • Methods:

    1. Inorder Traversal: Visit left subtree, current node, right subtree. Displays nodes in increasing order for a BST.

    2. Postorder Traversal: Visit left subtree, right subtree, current node. Useful for operations like finding directory size.

    3. Preorder Traversal: Visit current node, left subtree, right subtree.

  • Example Traversals in a defined tree:

    • Inorder Example: 45 55 57 59 60 67 100 101 107

    • Postorder Example: 45 59 57 55 67 101 107 100 60

    • Preorder Example: 60 55 45 57 59 100 67 107 101

Tree Interface and Design Patterns

  • Tree Interface: Defines common operations for trees such as search, insert, delete, traversals, etc.

  • AbstractTree Class: Partially implements the Tree interface, allowing concrete classes to extend it,

    • For instance: AbstractTree and a BST class can be defined to extend from it.

  • Concrete Classes: Implementation of specific functionality (e.g., BST.java).

    • Contains methods for insertion, traversal, path retrieval, and elements deletions.

Deleting Elements in a BST

  • Deletion Process: Locate the node to be deleted and its parent.

    • Case 1: Node has no left child; connect the parent to the right child.

    • Case 2: Node has a left child; perform operations to replace the value and handle child connections accordingly.

  • Example: For a node deletion, logic is executed to manage children correctly while maintaining the BST properties.

Time Complexity

  • Traversal Complexity: $O(n)$ for inorder, preorder, and postorder traversals.

  • Search, Insertion, Deletion Complexity: Relies on the height of the tree, which in the worst-case scenario is $O(n)$.

Practical Example

  • Program Application: Program designed to create and manipulate a binary tree, with specific focus on string data insertion and traversals. See files like TestBST.java for practical implementations.

  • Method Limitations: inorder(), preorder(), and postorder() display elements but cannot be utilized for processing elements directly within the tree structure.