Chapter 15 — Speeding Up All the Things with Binary Search Trees

Tree

A node-based data structure where nodes can connect to multiple child nodes

Root

The top node of a tree

Parent

A node that has child nodes below it

Child

A node below another node

Descendant

Any node that stems from another node

Ancestor

Any node above another node in its path

Level

A row of nodes in a tree

Binary tree

A tree where each node has zero, one, or two children

Binary search tree

A binary tree where left descendants are lesser values and right descendants are greater values

BST

Short for binary search tree

BST left rule

Values less than the current node go to the left

BST right rule

Values greater than the current node go to the right

BST search

Start at the root, compare the target, then move left or right

BST search left

Search left if the target is less than the current node

BST search right

Search right if the target is greater than the current node

BST search found

Stop when the current node equals the target value

BST search not found

Stop when the search reaches a dead end or null child

Balanced tree

A tree where subtrees are spread out evenly

Imbalanced tree

A tree where one side has many more nodes than the other

Balanced BST search Big O

O(log N), because each step moves down one level and eliminates many nodes

Imbalanced BST search Big O

O(N), if the tree becomes like a linked list

Why balanced BST search is fast

Each comparison eliminates either the left or right side of the tree

BST levels and log N

A balanced tree with N nodes has about log N levels

BST insertion

Search for the correct empty spot, then insert the new node there

BST insertion average Big O

O(log N), if the tree is balanced

BST insertion worst case

O(N), if the tree is badly imbalanced

Order of insertion

The order values are inserted can affect whether the tree becomes balanced or imbalanced

Sorted insertion problem

Inserting sorted values can make a BST act like a linked list

Randomized insertion benefit

Random insertion order can help create a more balanced tree

BST deletion

Removing a node while preserving the binary search tree rules

Leaf node

A node with no children

Delete a leaf node

Remove it directly from the tree

Delete node with one child

Connect the deleted node’s parent to the deleted node’s child

Delete node with two children

Replace it with its successor node

Successor node

The smallest value greater than the node being deleted

Finding a successor

Start at the right child, then keep going left until there is no left child

Rightmost node

The greatest value in a binary search tree

Find greatest value

Keep moving right until there is no right child

Ordered array vs BST

Both can search in O(log N), but BSTs can insert faster when balanced

Main lesson of Chapter 15

Binary search trees keep data ordered while allowing efficient search, insertion, and deletion when balanc