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