IB Computer Science Topic B4.1.4: Explaining the Structures and Properties of Bsts Notes

A BST Keeps Data Sorted by Where Each Value Is Stored

1. A binary search tree (BST) is a binary tree in which every node has at most two children and one ordering rule holds at every node.
2. The left subtree of a node holds only values smaller than that node, and the right subtree holds only values greater.
3. The rule covers whole subtrees, not just the two immediate children, which is what lets a search throw away half of what remains at every step.
4. No value is ever sorted as a separate step; the position a value is inserted into is what keeps the tree in order.

The Vocabulary the Mark Scheme Expects

1. Root
   1. The single node at the top, and the starting point of every insertion, search and deletion.
2. Parent and child
   1. A node and the nodes directly below it, reached through its left and right references.
3. Leaf node
   1. A node with no children at all, so both its left and its right reference are null.
4. Subtree
   1. Any node together with everything below it, which is itself a valid BST.
5. Height
   1. The number of levels from the root down to the deepest leaf, which sets the maximum number of comparisons a search can need.

Sketching a BST From a Data Set

1. The first value inserted becomes the root.
2. Every later value walks down from the root, going left when it is smaller and right when it is larger, until it reaches an empty position.

The Tree Diagram That Data Set Produces

1. Everything to the left of 40 is smaller than 40, and everything to the right is larger, so the rule holds at the root.
2. 10, 30, 50 and 70 are the leaf nodes, because none of them has a child.
3. The height is three levels, so no search in this tree needs more than three comparisons.

Insertion Order Decides the Shape

Inserting the same values in ascending order, 10, 20, 30, 40, 50, gives every node a right child and nothing else.

1. This is a skewed tree; it still obeys the ordering rule, but it has degenerated into a linked list.
2. A search now has to visit every node in turn, so the structure has lost the whole advantage it was chosen for.

Searching, Inserting and Deleting Nodes

Search

1. Start at the root and compare the target with the value in the current node.
2. Go left when the target is smaller and right when it is larger, and stop when the two values match.
3. Reaching a null reference means the value is not in the tree, so the search returns false there rather than continuing.
4. Each comparison removes an entire subtree from consideration, which is why a balanced tree of 1,000 nodes needs about 10 comparisons rather than 1,000.

Insertion

1. Insertion runs exactly the same walk as a search, and puts the new node wherever that walk reaches a null reference.
2. The new node always arrives as a leaf, so no existing node has to move.
3. A duplicate value has no legal position under a strict left < node < right rule, so implementations either reject it or send every duplicate consistently to one side.

Deletion

1. Deletion is the only operation with more than one case, and which case applies depends on how many children the node has.
2. The node is a leaf
   1. Remove it and set the parent's reference to null.
3. The node has one child
   1. Set the parent's reference to that single child, which lifts the whole subtree up one level intact.
4. The node has two children
   1. Replace the node's value with its in-order successor, the smallest value in its right subtree, then delete that successor from its original position.
   2. The in-order successor is used because it is the next value in sorted order, so the ordering rule still holds everywhere after the swap.

The Same Deletion as a Diagram

1. Nothing else in the tree moves, because only the deleted node and its successor change position.
2. Checking the result is a two-second job: run an in-order traversal and confirm it is still ascending.

Traversal: Where the Node Itself Is Visited

1. The name of a traversal says where the node is visited relative to its two subtrees, so the name is the rule.
2. Pre-order visits node, then left, then right.
3. In-order visits left, then node, then right.
4. Post-order visits left, then right, then node.
5. In-order traversal of a BST returns the values in ascending order, which is the cheapest way to get sorted output from the structure.

How BSTs Are Used to Organize Data

1. Sorted lookups over changing data
   1. Values stay in order as they are inserted and deleted, so no re-sort is ever needed after a change.
2. Database indexing
   1. An index held as a tree lets a query narrow the rows to check at each level instead of scanning the whole table.
3. Range queries
   1. An in-order traversal that starts at one value and stops at another returns everything between them without examining the rest of the tree.
4. Symbol tables in a compiler
   1. Identifiers are inserted as they are declared and looked up in about log n comparisons each time they are used.

Performance Against Other Structures

A BST is worth choosing when data changes often and has to stay in order, and it is the wrong choice when the input arrives already sorted.

The skewed column is why a question that states the data arrives in ascending order is testing whether you spot the degenerate case.