INB371 Week 7 Lecture

3 Pages
Unlock Document

Malcolm Corney

INB371 Week 6 Lecture Trees 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 Binary Trees 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. Set ADT In a set ADT, the value of the element identifies the key value for lookups. Values must be unique and can’t be modified. Map ADT 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 TreeNode 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 to th
More Less

Related notes for INB221

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.