CS61B Guide

Search…

Object Oriented Programming

Abstract Data Types

Sorting

Binary Trees

"The most important concept in computer science" - Josh Hug

Humble Origins

Linked lists are great, but we can do better! Let's try **rearranging the pointers **in an interesting way.

Instead of starting at one end of the list, let's set our first pointer at the **middle** of the list!

Now, let's make new pointers going to the **center **of each **sublist **on the left and right of the center.

Let's do it again!

Would ya look at that, we've got a **tree**! 🌲

🌲🌲🌲🌲🌲

Types of Trees

Right now, we can determine some properties that all trees have.

- All trees have a
**root node**. - All nodes can point to
**child nodes.**Or, if they don't have any children, they are**leaves.**

We can add more and more constraints to our tree to make them more useful!

First, let's add the constraint that **node can only have 2 or fewer children **to create a **binary tree.**

Then, let's **ensure our tree is sorted **to create a **binary search tree. **A tree is sorted if it has these properties:

- Every value in the
**left subtree**of a node is**less than**the node's value. - Every value in the
**right subtree**of a node is**greater than**the node's value. - Values are
**transitive**- there are**no duplicate values**. - The tree is
**complete**- it is possible to**compare any two values**in the tree and say that one is**either less than or greater than the other.** - The tree is
**antisymmetric**- If`p < q`

is true and`q < r`

is also true, then it must follow that`p < r`

.

Tree Operations

There are **three important operations** that trees should support: **find, insert, and delete.**

Finding a value in a tree uses Binary Search. Click the link below to read up on it!

Insert

The insert algorithm is **very similar to binary search.** Here are the steps to take:

- Search for the item.
**If it's found, then do nothing**since the value is already in the tree. - If it's not found (search would return null in this case), then create a node and put it where it should be found. If using recursion, this last step is already done- all we need to do is return a new node!

Here's the algorithm:

public BST insert(BST T, Key sk) {

if (T == null) {

// Create new leaf with given key. Different from search

return new BST(sk, null, null);

}

if (sk.equals(T.key)) {

return T;

} else if (sk < T.key) {

T.left = find(T.left, sk); // Different from search

} else {

T.right = find(T.right, sk); // Different from search

}

}

Delete

This one's a bit trickier because we need to make sure that the new tree still **preserves the binary search tree structure. **That means that we might have to shuffle around nodes after the deletion. There are **three cases:**

A) The node to delete is a **leaf**. This is an easy case- just remove that node and you're done!

Deleting a leaf.

B) The node to delete has **one child. **In this case, **swap** the node with its child, then **delete the node.**

Deleting a node with one child.

C) The node to delete has **two children.** This one's trickier, because we still need to preserve the tree structure! In this case, we have to **traverse the node's children **to find the **next biggest value **and swap that up to replace the old node.

Deleting a node with two children.

Asymptotic Analysis

A binary tree can be **bushy **or **spindly. **These two cases have dramatically different performances!

A bushy tree is guaranteed to have a height of

$\Theta(\log(n))$

which means that the runtimes for adding and searching will also be $\Theta(\log(n))$

.A spindly tree has a height of

$\Theta(n)$

which means that the runtimes for adding and searching will also be $\Theta(n)$

.Limits of Trees

While trees are extremely versatile and fantastic for a variety of applications, trees have some limitations that make it difficult to use in some situations.

**All items in a tree need to be comparable.**We can't construct a binary tree out of categorical data, like models of cars, for example.**The data must be hierarchical.**If data can be traversed through in multiple ways, or forms loops, Graphs are probably better.**The best case runtime is**$\Theta(\log(n))$. This might seem good, but other data structures like Tries and Hash Tables can be as good as$\Theta(1)$!

Tree Traversals

Check out these pages for information on how to go through each element of a tree!

Last modified 2yr ago

Copy link

On this page

Humble Origins

Types of Trees

Tree Operations

Find

Insert

Delete

Asymptotic Analysis

Limits of Trees

Tree Traversals