Trees Flashcards
How would you define a tree informally? How can it be implemented in programming?
An abstract data type for hierarchical storage of information.
In programming we can set a pointer at root and then move to an arbitrary element as they are all connected
What is a rule about elements, that root and the ends (leafs) of the branches don’t follow?
Each element has a parent and zero or more children
Can you think of some examples of trees?
Linux directory structure
Family tree
Do you remember the formal definition of a tree?
A tree T is a non-empty set of nodes storing useful information in a parent-child relationship with the following properties:
- T has a special node r referred to as the root
- Each node v of T different from r has a parent node u
What do we call external and internal nodes?
External -> leaf node -> 0 children
Internal -> 1 or more children
What about the formal definition of a sub-tree (rooted at node v)?
A tree consisting of all the descendants of v in T including v itself
How would you describe an ordered tree?
A tree where a linear ordering relation is defined for the children of each node, i.e we can see an order in each level.
How would you describe an ordered binary tree? When is it proper?
It is an ordered tree where each node has at most two children. The tree is proper if each internal node has two children (these are labelled left and right child and left comes before right)
What is an application of a binary tree?
Arithmetic expression evaluation. Easily apply a traversal algorithm on a binary tree where leaves are numbers and internals are operations.
More on programming implementation of trees, how can we access the abstract tree data type?
Using Accesor methods , root(),
parent(v), returns pointer parent node of v
and children(v), returns iterator for children which may
be empty
What are more methods that we need on the abstract tree datatype other than the accessors?
Query: isInternal, isExternal, isRoot
Generic: size, elements (i.e iterator of elements at nodes), positions (i.e iterator of all nodes), swapElements(v,w), replaceElement(v,e)
What at the complexities of tree ADT methods?
NOT ADDED YET
There’s another method we could define to return the depth of a tree T. What is depth of v? What type of algorithm is used to calculate this?
It is the number of ancestors of v, excluding itself.
The depth algorithm is recursive: base case, root depth is 0, step case depth of v is one plus depth of parent.
There’s another method we could define to return the height of a tree T. What is height of T? What type of algorithm is used to calculate height of v in T?
height of T = the maximum depth of an external node of T. A recursive algorithm: base case, if v is external height is 0, else it is 1 _ max height of child of a child of v
What is tree traversal best described as?
A systematic way of accessing all the nodes of T
What are the two different traversal schemes?
Preorder: root visited (and action performed on it )first then subtrees at children visited recursively. action BEFORE calling on subtree
Post order: action after calling on subtree
When is preorder traversal useful? What is it’s time complexity?
Produce linear ordering of the nodes in a tree where parents are always before their children.e.g for book example. Time complexity is O(n)
When is postorder traversal useful?
Calculating arithmetic expression, finding size of directory
What additional accessor methods do binary trees support? What extra annotation can we use on the nodes?
Leftchild(),RightChild(),sibling()
We can now use levels to denote all the nodes of a binary tree at the same depth d as the level d of T
If m the number of nodes on level c and n the number of nodes on level d how many times m is n ? (n = X*m)
X = 2
What is in-order traversal? What trees can it be performed on?
In order traversal is like a combination of post and pre
Can be performed on binary trees.
What data structure could we use to represent a binary tree?
A vector bases structure: Based on simple way of numbering the nodes of T (level numbering function p(v)).
What are 2 disadvantages of storing a binary tree in an array, based on a numbering function?
If the tree is not proper there will be blank spaces in the array.
May not have the best performance.
What is a more space efficient way to to store a binary tree?
Linked structure. Nodes represented by an object that references element v, and the positions associated with parent and children.
