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

Contains

The contains method uses Recursion. The basic approach boils down to handling four possible cases as we recurse through all the nodes in the tree:

We have reached an empty node, and should return false to the method that called us
Our element is less than the search target, and we should go left
Our element is greater than the search target, and we should go right
Our element is just right, and this node is equal to the search target

def contains(target, node):
    if(node is null):
        return false
    elif target < node.getvalue():
        return contains(target, node.left)
    elif target > node.getvalue():
        return contains(target, node.right)
    else:
        return true

Binary Search Trees

From charlesreid1

Contents