INB371 Week 6 Lecture
Tree structured hierarchies exist in many contexts. They are used in biological
classifications for living organisms. They are also used for businesses, so that each
employee reports to a single supervisor, up to the CEO at the root. File systems also
use tree systems.
Family trees provide a lot of the terminology for the Compsci tree structure.
Parent and child relationships can be modeled with pointers, so that there’s a direct
link between a parent node and achild node. Each node can contain data specific to
that node (if you’re modeling a family tree, you’d have the name as the data of the
node), and then pointers to its children. The Node would be a struct or a class, and
then tree as a pointer to a Node. Trees are pointers to nodes, and nodes contain
trees. If you isolate Henry I on the previous slide, the structure of nodes below is a
‘tree’. You could call this a subtree.
Picture of data structure of tree on slides
In a binary tree, each tree has at most 2 children. Every node except the root is
designated as either a left or right child of its parent.
Binary Search Tree
Every node contains a value called a key, which defines the order of the nodes. You
can put any data type into the key, just as long as that datatype implements some
type of ordering, which allows you to indicate less than/greater than. The primitive
types like int and char have built in orderings, but if you define your own class you’d
have to define an ordering (as last week in lecture with operator overloading) In a
binary search tree the key values are unique. You can’t store two nodes with the
same key value. What makes binary search powerful is that at every node, the key
value must be greater than the keys in the nodes left subtree and the key must be
less than all the keys in the right subtree.
In a set ADT, the value of the element identifies the key value for lookups. Values
must be unique and can’t be modified.
In a Map, the value of an element is identified by a separate key. The key is the
student number, the value is your student record. Again, keys must be unique and cannot be modified, but the values stored with a key CAN be modified, so we can
update the data associated with a specific key.
Set and Map ADT
The efficiency of a set and map are similar in the sense that we’ll be doing the same
operations, but with different efficiencies. IT would be nice if we could accomplish a
log n search for a binary search. And an o(1) insert/delete. We can’t do any better
than O(N) for traversing all the elements. There could be other operations we may
like as well such as Size and isEmpty, and even Clear. The Binary Search Tree can
provide these capabilities.
Binary Search Tree Construction
The treeNode is the basis of the binary search tree. It consists of the key, left child
and right child. The children are pointers to more treenodes.
The advantage of a Binary Search Tree is the ability to use the binary search
algorithm to find a particular node. When looking for F, F is larger than E so it goes