DOC PREVIEW
TRINITY CSCI 1321 - Binary Trees

This preview shows page 1-2-3-4-5 out of 14 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 14 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Binary Trees4-6-20062Opening Discussion■What did we talk about last class?■Base case for longest path.■Do you have any questions about the assignment?3Faster Sorting●Let's review the faster sorts and look at code for the second.–Mergesort repeatedly divides the array in two doing little work until it gets down to one element. Then it merges sorted arrays as it comes back up. This can't be done in place. Always O(n log n).–Quicksort picks a pivot and puts all other elements before or after the pivot then recurses on sides. Does work going down. Generally O(n log n).4What is a Tree?●You are all familiar with what normal trees look like. In CS we use the term somewhat differently, and more formally.●To describe trees we need some basic terminology–Node - an element of a tree. One node is designated as the “root”–Edge - a directed connection from one node to another.5Tree Criteria●Every node, C, has exactly one incoming edge from another node, P. P is said to be the parent of child node C. Root has 0.●There is a unique path from the root to any node. The number of edges on that path is called the path length. It is also called the depth of the node.●A node with no children is called a leaf. The path length from a node to the deepest leaf in the height of that node.6More Terms●Following the parent-child analogy, children of the same node are called siblings. We also call any node on a path below a given node a descendant and any above an ancestor.●You might also hear the size of a node referred to as the number of descendants of a node, including itself.●We can also define a tree as either empty, or a root with zero or more subtrees where the root connects to the roots of those subtrees.7General Tree Implementation●In a general tree, each node can have zero or more children. That is a lot of flexibility. We want a class to represent nodes. To get this flexibility we can use a linked list. Each node has pointers to a first child and the next sibling.●It might be just as easy to have the child member be a Vector that we put Nodes in. File systems are a good example of this.8Traversals●As with any data structure one of the things you want to be able to do is to traverse through all the elements.●Think for a while about how you would do this? There is even a question about the order you traverse them in. Do you want to process a node before you process its children or after? If before we call it a preorder traversal. If after it is a postorder traversal.9Traversals and Recursion●The simplest way to do a traversal is through recursion. If you want to do it with a loop you have to implement a data structure to store some nodes or have the tree specially set up.●The traverse function takes a node and calls itself once with each child node. It also does whatever the visit operation is.●Preorder does a visit before going to children and postorder visits after going to children.●Breadth first uses a queue, not recursion.10Binary Trees●Sometimes we want to limit how many children a node has. One of the most commonly used trees in programming is the binary tree where no node has more than 2 children.●The children are often called left and right. Your book has a fair bit more discussion of binary trees that we won’t go into right now but you should look at.11In-order Traversal●For a binary tree there is an extra type of traversal called an in-order traversal where the node is visited between the recursion down left and right.●Equations are great examples of trees. We typically write them out in the in-order. We could just as well write them out in post-order or pre-order.12Sorted Binary Trees●One of the best uses of binary trees is the sorted binary tree. In this type of tree, we store data in every node and below any node we put lesser values to the left and greater values to the right.●We find elements by going down the tree always going left or right. This gives us behavior like a binary search, but the tree is more flexible because adds and removes are quite efficient as well.13Adding and Removing●The code for both adding and removing from a binary tree begins like a search that keeps track of previous (much like a linked list).–The add always goes to a leaf and adds the new element to the proper side.–The remove replaces the node we are removing with either the greatest node on the left or the smallest node on the right.14Minute Essay■What would a binary tree look like if you added the numbers 5,3,8,1,6,2,9 in that order?■Remember that the design for assignment #6 is due


View Full Document

TRINITY CSCI 1321 - Binary Trees

Documents in this Course
Recursion

Recursion

11 pages

Iterators

Iterators

10 pages

Actors

Actors

9 pages

Recursion

Recursion

15 pages

Recursion

Recursion

10 pages

Threads

Threads

7 pages

Trees

Trees

11 pages

Load more
Download Binary Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Binary Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Binary Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?