Binary Search Trees

Notes

Definitions

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

Weiss

Weiss, Data Structures in C++, covers binary search trees in Chapter 4, covering trees generally. This book is a good advanced data structures textbook, so it moves through trees quickly and spends most of its time on detailed implementations of types of trees.

The binary search tree covered on page 133 of the textbook provides an entire abstract data type that is as follows:

• Class name is BinarySearchTree
• Data member is pointer to root node (null for empty trees)
• public member functions use general technique of calling private recursive functions
• insert, remove, contains
• find min, find max
• binary node class:
  • single element of data
  • left pointer
  • right pointer