trees 🌲

trees as a form of data structure

e.g. file system

trees are connected graphs that has:

• edges (lines) and nodes (circles)
• no cycles (can’t get caught in loops)
• each node with a particular data value (an ‘item’)
• each node links to up to $k$ children

key terms describing trees

root = node with no parents (the ‘start’ of the tree)

internal node = node with both parent(s) and children

leaf = node with no children

parent node =

child node =

binary search trees (BSTs) ✌️

tree where $k=2$ (each node has two children)

why we need binary trees

binary search is a necessary algorithm to use for large sets of numbers (much quicker than linear search) — but it requires a sorted structure

arrays have

• quick look up (binary search)
• slow at insertion / deletion (whilst maintaining order)

linked lists have

• quick insertion (whilst maintaining order)
• slow look up (binary search)

a binary tree tries to take the ‘best of both worlds’

instead of using complex algorithms to do these operations, we will instead store the data in a complex data structure to simplify our algorithms

(note: the trade-off between time and memory usage)

definition + properties

BSTs have a recursively defined structure: a BST either is

• empty (NULL); or
• consists of a node with two subtrees
  • node contains a value
  • left and right subtrees are themselves binary trees

BSTs are ordered trees

• each node is the root of two subtrees (which may be NULL)
• all values in the left subtree are less than the root
• all values in the right subtree are greater than the root
• these two rules apply for all nodes in the tree

some key terms:

• level of a node = path length from root to node (root is level 0, direct children have level 1 etc.)
• height/depth of tree = max path length from root to any leaf
• balanced BST = a tree is height-balanced once there are equal number of nodes between the left and right subtree for all nodes in the tree

operations

some possible operations include

• insert(Tree, item)
• delete(Tree, item)
• search(Tree, item)
• print(Tree)
• (create + delete)
• join(Tree, Tree) — a helper function mostly used in TreeDelete