Binary Search Trees

Notes

Formal Definition of a Tree

Rooted binary tree is recursively defined as being either (1) empty, or (2) consisting of a node called root, with two rooted binary trees called the left and right subtrees.

Skiena Section 3.4

Binary search requires fast access to two elements - the media elements above and below the given node.

Search trees utilize this fact and a linked structure to create binary search trees.

Binary search tree labels each node in the binary tree with a single keys such that for any node labeled x, all of the nodes in the left subtree of x will have keys < x,while all nodes in the right subtree of x will have keys > x.

For any binary tree on n nodes and any set of n keys there is exactly one labeling that makes it a binary tsearch tree.

Implementation

Implement via:

• left and right pointer fields
• optional parent pointer

Operations:

• searching
• finding minimum/maximum element
• traversal (in order)
• insertion
• deletion

balanced search trees:

• trees exist, and can be used as black boxes.
• suppose that we have access to a balanced dictionary or tree data structure - and go from there.
• insert should automatically balance the tree