Trees Flashcards
What is a ‘Tree’ and what is the main benefit of storing data in a tree?
Trees: A hierarchical/ nested structure.
Storing data in trees allows us to speed up O(N) algorithms to O(lgN). This is because if the tree is fully balanced we can eliminate half of it.
Describe the Tree ADT and its basic operations.
Elements of a Tree:
r: root node
Non-Empty subtrees (T1, T2, …, Tn) each connected by a ‘directed edge’ from r.
Operations:
get(), size(), set(), add(), remove(), find()
Tree Terminology:
Root: The top of the tree.
Internal Nodes: Nodes that have both a parent and a child.
Child: Bottom nodes, that are only connected to a parent.
Siblings: Nodes that share a common parent.
Define the ‘Depth’ of a tree.
The total number of edges from the root node to the leaf node in the longest path.
Root Node Height : 0
What is a ‘Binary Tree’?
A k-array (k=2) data structure where every node has at most two children.
What is the typical runtime of a binary tree?
lg N
What is a ‘Full’ binary tree?
A tree in which every node is a leaf or has two children
What is a ‘Complete’ binary tree?
When all levels (except the last) are completely filled and every node is as far left as possible.
What is the ‘Diameter’ of a binary tree?
The number of nodes on the longest path between any two nodes.
What is the ‘Width’ of a binary tree?
The number of nodes on the level w/ the most node.
What are the three most common types of tree traversals?
Preorder: Root L R
Inorder: L Root R
Postorder: L R Root
What is a ‘Binary Search Tree” (BST) and what is its main advantage?
A binary tree where for each node on the tree:
- All Nodes in the left subtree contain nodes that are < than the root.
- All Nodes in the right subtree contain nodes that are > than the root.
Its main advantage is that it can be used as a tree map
Describe the BST data type, its purpose, and its operations.
Its keys are unique, but its values are not.
Goal: Reduce finding an item to O(ln N)
Operations: insert(x), contains(x), findMin(), findMax(), remove(x).
What is an ‘AVL Tree’?
A BST in which the following balance condition holds after each operation.
For all nodes, the height of the left subtree and the right subtree differs by at most 1.
What is the height of an AVL Tree?
At most 0(lnN).
What are the two types of AVL tree imbalances, and their corresponding rotations?
Outside Imbalance:
rotateWithLeftChild:
An insertion into the left subtree of the left child.
rotateWithRightChild:
An insertion into the right subtree of the right child
Inside Imbalance:
doubleWithLeftChild: LR
An insertion into the right subtree of the left child.
doubleWithRightChild: RL
An insertion into the left subtree of the right child.
What is ‘Structural Induction Over Trees’ and what are its two forms?
Proof by structural induction is used to prove properties over trees.
Its two most common forms are:
1. Structural Induction over the height of a tree
@. Structural induction over the number of nodes in a tree
What is the poof template for structural induction over trees?
Base Case: The property holds for a single node.
Inductive Step:
1. Assume the property holds for each possible subtree by proving K.
2. Show that it holds for all trees by combining the subtree w/ a parent. K+1
Describe structural induction over ‘height’ proof?
Goal: Show a ‘perfect’ BT of height h has 2^(h+1) - 1nodes.
Base Case: A tree of height 0 has 2^(0+1) - 1 = 1 node.
Inductive Step:
1. Assume that a perfect binary tree of height k has 2(k+1) -1 nodes.
- Show that any perfect BT of height K+1 has 2^(k+1)-1 nodes with a recursive construction.
- Therefore a Binary tree…
Notes:
A perfect tree is an upper bound.
A BT of n nodes has at least height ln(n+1)-1.
Describe structural induction over the ‘number of nodes’ in a tree.
Goal: Show a ‘full’ BT of N nodes has (N+1)/2 leaves.
Base Case: A tree w/ 1 node has (1+1)/2 = 1 leaf.
Inductive Step:
1. Assume a full tree 1/K nodes has (K+1)/2 leaves.
2. In a Full BT w/ K+2 noes, there must be at least 1 internal node w/ 2 leaves as children
- Removing these children yields a tree w/ K nodes
3. The new tree of k+2 nodes has [(k+2) + 1]/2 childrn
