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