Part 3 Flashcards
Stacks and queues are examples of ________ adts
Linear
Trees are ____________ ADTs
Non-linear / Recursive
The child of a tree has the type
Tree
A tree with no children is called
A leaf
What word is used to refer to positions in a tree?
Node
The root node of a tree is a node with no _____
parent
What makes a tree a binary tree?
Each node will have no more than 2 children
What are the primitive operations of binary trees, and their semantics?
createtree - creates a new empty tree
maketree - takes data item, two trees and creates a new tree with the data item in the root and two trees as children
isempty - deduce whether the tree is empty
leftchild/rightchild - return references to the children
value - return the data item at the root (node)
What are the three orders of tree traversal?
pre-order
post-order
in-order
what is pre-order traversal?
visit root, then left child in pre-order, then right child in pre-order
what is post-order traversal?
visit the left child in post-order, then the right child in post-order, then the root
what is in-order traversal?
visit he left child in-order, then the root, then the right child in-order
What is binary chop?
Look at middle of array, if its greater than the number searching for, look at middle of left half, else middle of right half & repeat till you find the number
What is a binary search tree?
A binary tree where all the left children are less than the root and all the right children are greater
How are non-binary trees typically implemented?
Left child right sibling
What is the left-child-right-sibling representation?
Each node may has one child
More than one child = the children are stored as references from the first child
A
/
B - C - D
/
E
When deleting a node in a binary search tree, if the node has one child, what is the procedure?
Replace the reference from the parent to the node with a reference to the node’s child
When deleting a node in a binary search tree, if the node has two children, what is the procedure?
Replace the reference to the node with a reference to either largest value in left child or smallest value in right child
The time taken for insertion, deletion and searching binary search trees are approximately ________
proportional to the depth of the tree
What is the average depth of a binary search tree if the items are inserted in a random order?
2.5log2n
What are the average and best times for insertion deletion and searching (big O)?
Average: O(logn)
Worst: O(n)
When writing a generic class how can it be restricted so the Type must extend comparable?
public class BST<t>></t>
