Introduction

• We can improve linked lists by making them doubly linked as well as created a tail pointer

Why is it Important?

• Trees are some of the most used data structures in computer science. They link information together in a relational way. You can use them to sort, to store information, to make inferences, and so much more. They are even used in databases to help index (find) the data in the database.

Lesson Notes

Trees

• Trees are known as a hierarchical data structure. Instead of pointing from one piece of data to the next, a tree has many different paths that you can take from each node. This creates a system of parents, and children.

• Parents are the nodes that are directly above another node, while children are ones that are directly below. For example, node 23 is a child of node 17, and node 17 is therefore the parent of node 23. However, the relationship is only a direct relationship. So, node 67 is not a child of node 23, even though it’s one layer lower.

• The layers of the tree are also important. They are known as the height of tree. Trees are also typically one directional, so you go from parent, to child, to child, to child, etc. You don’t typically go back up the tree for any purpose, except maybe a printing of the tree.

• You also have nodes called “leaves”. These are the nodes without any children, meaning they are at the end of the tree structure. Once you reach them, you cannot go any further in the tree.

Tree Structures

• Trees can have a variety of structures. They can have a set number of children or have an infinite amount. It all comes down to how you want to use them. A special type of tree however is known as the Binary Search Tree (BST).

Binary Search Tree

• A binary search tree is a tree with these rules:
  • Each node can only have at most two children
  • All right children must be greater than
  • All left children must be less than or equal to

• Through these rules we create a tree which can actually be used to search for things. Because we know the above rules, we can actually traverse the tree to find a number. The above picture is a binary search tree.

• Let’s see if 19 is in the tree. We take the root node (the one at the very top) 50, and ask, is 19 greater or less than this node of 50? Well, it’s less. So we look at the left child. 50->17. We then ask the same question, is 19 greater or less than 17? It’s greater, so we take the right child. 50- >17->23. Now is 19 greater or less than 23? It’s less than. We take the left child, and there we have it, the number is in the tree.

• If the number were for example, 22, we would do the same procedure, and find out that when we tried to look at the right child of 19, there is nothing there. We would then return that no, 22 is not in the tree.

• So with this ability to search the tree with only touching a few elements, we get some great time efficiencies with this.

• (This assumes random order of inserting. If you insert a series of consecutive numbers, you will grow the tree in a straight line, making all operations the same as a list, so O(n). There are more advanced trees known as red-black trees and AVL trees that make sure this never happens. But they are quite complex)

• Search: O(log n) – We only have to touch log elements (the height of the tree) to figure out if the element is in the list or not.

• Insert: O(log n) – Same with inserting in to the tree. We ask the same questions as above, and find the empty place in the tree, and insert there.

• Delete O(log n) – Same as the rest, we can delete by just asking the same questions.

Quiz

Applications