Binary Search Trees Notes

Basic Concepts and Binary Search Trees

• Linear list structures: Arrays vs. linked lists.
  • Involve search, insertion, and deletion algorithms.
• Binary Search Trees (BST):
  • Efficient for searching, inserting, and deleting data.
  • A BST is a binary tree with specific properties:
    • All items in the left subtree are less than the root.
    • All items in the right subtree are greater than or equal to the root.
    • Each subtree is itself a binary search tree.

BST Structure and Balance

• Key Property: In a binary search tree:
  • All nodes in the left subtree are less than the root node (All < K).
  • All nodes in the right subtree are greater than the root node (All > K).
• Tree Completeness and Balance:
  • Complete and balanced trees: (a) and (b) are examples.
  • Nearly complete and balanced tree: (d) is an example.
  • Neither complete nor balanced trees: (c) and (e) are examples.

Invalid Binary Search Trees

• Figure 7-3 illustrates examples of invalid binary search trees.
• The key property of BSTs (left subtree < root < right subtree) must always hold.

BST Operations

• There are four basic BST operations:
  • Traversal
  • Search
  • Insert
  • Delete

Tree Traversals

• Preorder Traversal:
  • Visit the root first, then the left subtree, then the right subtree.
  • Example: 23 18 12 20 44 35 52
• Postorder Traversal:
  • Visit the left subtree first, then the right subtree, then the root.
  • Example: 12 20 18 35 52 44 23
• Inorder Traversal:
  • Visit the left subtree first, then the root, then the right subtree.
  • Example: 12 18 20 23 35 44 52
  • Inorder traversal produces a sequenced (sorted) list.

Right-Node-Left Traversal

• Right-Node-Left Traversal:
  • Visit the right subtree first, then the root, then the left subtree.
  • Example: 52 44 35 23 20 18 12
  • Right-node-left traversal of a binary search tree produces a descending sequence.

Searches in BST

• Three types of searches:
  • Find the smallest node
  • Find the largest node
  • Find a requested node

Finding the Smallest Node

• Algorithm 7-1: findSmallestBST(root)
  • Objective: Finds the smallest node in a BST.
  • Precondition: root is a pointer to a nonempty BST or subtree.
  • Returns: Address of the smallest node.
  • Steps:
    1. If the left subtree is empty, return the current node (root).
    2. Otherwise, recursively call findSmallestBST on the left subtree.

Finding the Largest Node

• Algorithm 7-2: findLargestBST(root)
  • Objective: Finds the largest node in a BST.
  • Precondition: root is a pointer to a nonempty BST or subtree.
  • Returns: Address of the largest node.
  • Steps:
    1. If the right subtree is empty, return the current node (root).
    2. Otherwise, recursively call findLargestBST on the right subtree.

Binary Tree Search

• BST Search:
  • Locates a specific node in the tree.
  • Comparison to Sequenced Array:
    • BST search resembles a binary search algorithm.

BST Search Algorithm

• Algorithm 7-3: searchBST (root, targetKey)
  • Objective: Search a binary search tree for a given value.
  • Preconditions:
    • root is the root to a binary tree or subtree.
    • targetKey is the key value being searched for.
  • Returns:
    • The node address if the value is found.
    • null if the node is not in the tree.
  • Steps:
    1. If the tree is empty, return null (value not found).
    2. If targetKey is less than the current node's key (root), recursively call searchBST on the left subtree.
    3. If targetKey is greater than the current node's key (root), recursively call searchBST on the right subtree.
    4. Otherwise, the targetKey is equal to the current node's key; return the current node (root).

BST Insertion

• Insertion Process:
  • Follow the branches of the tree to find an empty subtree where the new node can be inserted.
  • Insertions typically occur at a leaf node or a 'leaflike' node (a node with only one null subtree).

BST Insertion Examples

• Example scenarios of inserting nodes into a BST.
• Figures 7-8 (a) and (b) demonstrate inserting 19.
• Figures 7-8 (c) and (d) demonstrate inserting 38.

BST Insertion Algorithm

• Algorithm 7-4: addBST (root, newNode)
  • Objective: Insert a node containing new data into the BST using recursion.
  • Preconditions:
    • root is the address of the current node in the BST
    • newNode is the address of the node to be inserted.
  • Postcondition: newNode is inserted into the tree.
  • Returns: Address of the potential new tree root.
  • Steps:
    1. If the tree is empty, set root to newNode and return newNode
    2. Locate a null subtree for insertion:
       • If newNode is less than root, recursively call addBST on the left subtree.
       • Otherwise, recursively call addBST on the right subtree.

BST Deletion

• Deletion Cases: There are four possible cases when deleting a node:
  • Case 1: The node to be deleted has no children (it's a leaf node).
    • Solution: Simply delete the node.
  • Case 2: The node to be deleted has only a right subtree.
    • Solution: Delete the node and attach the right subtree to the deleted node’s parent.
  • Case 3: The node to be deleted has only a left subtree.
    • Solution: Delete the node and attach the left subtree to the deleted node’s parent.
  • Case 4: The node to be deleted has two subtrees.
    • Deleting a node from the middle of a tree can create unbalanced trees.

BST Deletion Strategy

• Objective: Maintain the existing structure of the BST as much as possible.
• Method: Find a suitable data value to replace the deleted node's data.
• Two possible approaches:
  1. Find the largest node in the deleted node’s left subtree and move its data to replace the deleted node’s data.
  2. Find the smallest node in the deleted node’s right subtree and move its data to replace the deleted node’s data.

BST Deletion Algorithm

• Algorithm deleteBST (root, dltkey)
  • Objective: Deletes a node from a BST.
  • Preconditions:
    • root is a reference to the node to be deleted.
    • dltkey is the key of the node to be deleted.
  • Postconditions:
    • Node deleted if found.
    • If dltkey not found, root remains unchanged.
  • Returns: true if node deleted, false if not found.
  • Steps:
    1. If the tree is empty, return false.
    2. If dltkey is less than the current node's key, recursively call deleteBST on the left subtree.
    3. Else if dltkey is greater than the current node's key, recursively call deleteBST on the right subtree.
    4. Else (node to be deleted is found):
       • Test for leaf node:
         • If there is no left subtree, make the right subtree the root and return true.
         • Else if there is no right subtree, make the left subtree the root and return true.
         • Else (node to be deleted is not a leaf):
           • Find the largest node on the left subtree.
           • Save the root in deleteNode.
           • Set largest to the largest node in the left subtree (using largestBST function).
           • Move the data in largest to deleteNode.
           • Recursively call deleteBST on the left subtree of deleteNode to delete the now-moved key of largest.

Threaded Trees

• Background:
  • Binary tree traversal algorithms typically use recursion or programmer-written stacks.
  • Using stacks can be more efficient than recursion for frequent traversals.
  • A threaded tree presents a third alternative.
• Definition:
  • In a threaded tree, null pointers are replaced with pointers to their successor nodes in a specific traversal order (e.g., inorder).

Building and Traversing Threaded Trees

• Building a Threaded Tree:
  1. Build a standard binary search tree.
  2. Traverse the tree and change the null right pointers to point to their inorder successors.
• Traversal:
  1. Locate the far-left node (the first node in the inorder traversal).
  2. Loop, following the thread (the right pointer) to the next node.
  3. Continue until a null thread (right pointer) is encountered, indicating the end of the traversal.
• Advantages:
  • No recursion or stack is needed for traversal.
  • Straightforward and efficient traversal process.