top of page
This site was designed with the
.com
website builder. Create your website today.Start Now

Trees

Tutoring > Data Structures > Trees

A useful ADT in computer science is a tree, which is a hierarchical data structure consisting of nodes linked together.

What is a tree?

A tree is a data structure where each node contains a value (or NULL) and has references (or links) to child nodes (children).

A parent is a node which has child nodes.

A leaf is a node with no children.

The root is the top most node in a tree - it has no parents. 

Siblings are nodes with the same parent (like brothers and sisters).

The height of a node is the length of the longest downward path between the node and a leaf.

Edges link the nodes together.

The depth of a node is it's distance from the root (how many edges are there?)

Types of tree - binary search tree (BST)

To be a binary search tree, a tree must first be a binary tree, and secondly, the value of each node must be larger than it's left child, and smaller than it's right child. This assumes no duplicate values.

The main benefit of a BST is that the nodes remain ordered such that searching for a particular node takes less time than if it was un-ordered.

Because of this ordering, insertion and deletion require a bit more effort in order to retain the order.

This is an efficient way of searching due to the ability to half the problem with each iteration. Each time a node is checked, we either know:

  • that it is the one we are looking for, or

  • which subtree, left or right to look in next.

Types of tree - binary tree

A binary tree is a tree where each nnde has at most two children. Each node can have no children or one or two. A binary tree with just one node is still a binary tree. In fact, a tree with no nodes (the empty tree) can also be called a binary tree.

 

Primitive operations on binary trees:

There are two types of constructor to build binary trees.

  1. EmptyTree which returns the empty tree (no nodes in it)

  2. MakeTree(v, l, r) which makes a tree with at least one value, that has a left and a right subtree. The subtrees can be empty.

 

  • isEmpty(t) where t is the tree, this tests whether or not t is empty.

  • root(t) returns the value at the root of the tree.

  • left(t) returns the left subtree.

  • right(t) returns the right subtree.

Types of tree - AVL tree

Named after it's founders (Adelson-Velskii and Landis), an AVL tree is essentially a self balancing binary search tree.

In order to qualify as an AVL tree, the heights of the two child sub trees of any node must differ by at most one. They can be equal heights, or differ by one, but that's it!

This is known as a height balanced tree.

bottom of page