Binary Search Tree

Motivation

I can haz O(logN)?

• insert
• delete
• search

Cheat Sheet: http://bigocheatsheet.com/

Definition

A binary search tree is represented by a linked data structure in which each node is an object. In addition to a key field, each node contains fields, left. right, and p.

~CLR p244

The keys in a binary search tree are always sorted in sucha a way as to satisfy the binary-search-tree property: If y is a node in the left subtree of x then key[y] <= key[x]. If y is a node in the right subtree of x then key[x]<=key[y]

~CLR p245

Attributes

• node
• size
• depth
• balance

Operations

• insert
• contains