Limited time offer 20% OFF StudySoup Subscription details

Georgia Tech - CS 1332 - Class Notes - Week 4

Created by: Samantha Notetaker Elite Notetaker

Georgia Tech - CS 1332 - Class Notes - Week 4

This preview shows pages 1 - 2 of a 5 page document. to view the rest of the content
background image CS 1332 Spring 2019  Trees  1/28    Characteristics  •  An ADT  •  Basically a linked list  Visualization of a linked list oriented vertically and traversing down  •  No cycles  •  Highly recursive  •  Categories  Shape  Order  Properties of movement   Binary trees   •  Heaps  •  Binary search trees  AVLs   •  Do everything a binary search tree does + more   •  Splay trees      Terms  •  Root: stored as a variable  Access all other nodes from root   •  Children:   Similar to next node   •  External / leaf nodes  Have no children  The boundary   •  Internal nodes  Every node that's not a leaf node      Hierarchy  •  Parent / grandparent   •  Siblings   Share same parents   •  Cousins   •  Subtree   Portion of tree that has same properties as larger whole   Any  group of connected nodes in the tree that contain all children/grandchildren of the  root      Depth & height  •  Depth: distance of a node to the root  Depth of root = 0  Root's children = 1  •  Height: distance of a node to its furthest leaf   Height of leaf = 0 
background image CS 1332 Spring 2019  •  Ex from diagram (eq. will helpful on HW)  §   Height(g) = 1 + max(height(a), height(c)) = 2  •  G has 2 children, a & c; a has no children, C has 3 (all leaves)   Height of null/empty tree = -1     Tree ADT Operations  •  Information methods  size()  isEmpty()  iterator()  position()  •  Returns a list of positions of nodes  •  More customizable, depends on how you implement it   •  Accessor methods   root()  parent(x)   •  Returns parent of node x  •  Sometimes you keep track of parents, other times just children  §   For HW we will not be keeping track of parents   children(x)  •  Returns children of node x   numChildren(x)  •  Query methods  isInternal()  isExternal()  isRoot()          

This is the end of the preview. Please to view the rest of the content
Join more than 18,000+ college students at Georgia Institute of Technology who use StudySoup to get ahead
School: Georgia Institute of Technology
Department: Computer Science and Engineering
Course: Data Struct & Algorithms
Term: Spring 2019
Tags: java, Trees, and bst
Name: Week 4 Notes: Trees
Description: Covers general Tree overview, Binary Trees, Binary Search Trees, and BST Traversal. Some material overlaps between the 3 documents- this is just how it was covered M,W,F
Uploaded: 02/05/2019
5 Pages 48 Views 38 Unlocks
  • Better Grades Guarantee
  • 24/7 Homework help
  • Notes, Study Guides, Flashcards + More!
Join StudySoup for FREE
Get Full Access to GATech - Class Notes - Week 4
Join with Email
Already have an account? Login here
×
Log in to StudySoup
Get Full Access to GATech - Class Notes - Week 4

Forgot password? Reset password here

Reset your password

I don't want to reset my password

Need help? Contact support

Need an Account? Is not associated with an account
Sign up
We're here to help

Having trouble accessing your account? Let us help you, contact support at +1(510) 944-1054 or support@studysoup.com

Got it, thanks!
Password Reset Request Sent An email has been sent to the email address associated to your account. Follow the link in the email to reset your password. If you're having trouble finding our email please check your spam folder
Got it, thanks!
Already have an Account? Is already in use
Log in
Incorrect Password The password used to log in with this account is incorrect
Try Again

Forgot password? Reset it here