Week 7 Flashcards
What is a tree?
It is a hierarchial data structure.
It is a collection of vertices(nodes) and edges(arcs)
What is a vertex? What is an edge?
A vertex is like a node. It contains data and pointer information.
An edge connects 2 vertices.
How many descendants is a binary tree allowed. How about a Ternary tree?
A binary tree is allowed two.
A ternary tree is allowed three.
What is a parent node, a child node, a sibling and a leaf node?
Each node, except the root has only one node above it. It is called the parent node.
A node may have zero or more children, drawn below it.
Nodes with the same parent are called sibilings.
Nodes with no children are called leaf nodes. (Or terminal or external nodes).
What is a subtree? What is a forest? What is a level?
Any node can be the root of the subtree. A subtree consists of it and the nodes below it.
A set of trees is called a forest.
A tree consists of levels. The farther down you go, the higher the level.
What is height (depth), and path length?
The height (depth) of a tree is the distance from the root to the nodes furthest away.
The path length is the total sum of edges from each node to the root.
What is a binary tree?
Are trees where every node has 0, 1, 0r 2 children.
Each node contains data, a left child pointer, a right child pointer, (a parent pointer which is optional).
It can be uni or bi directional.
Has a root pointer which points to the root node.
What are Binary Search Trees?
Also called ordered binary trees.
Are organized so that every left child is less than or equal to the parent node.
Every right child is greater than the parent node.
What is the best case for a binary search tree?
What is the complexity for searching?
In the best case, the tree is balanced and the height is minimized.
This occurs when the height of the left and right subtrees of any node differ by no more than 1.
The complexity is O(log n).
What is the worst case for a binary search tree?
In the worst case, the tree degenerates into a linked list. Height is n-1.
What is the approximate height of a balanced tree?
It is approximately log n
How is insertion done in a binary search tree.
Insertion requires a search of the existing tree to find the parent node of the new node.
New nodes are always added as leaf nodes.
If the tree is empty, then the new node becomes the root node.
What are the two types of traversal in a binary search tree?
Depth first: recursively visits each node starting at the far left.
Breadth-first: starting at the highest level, move down level by level, visiting nodes on each level from left to right.
What is the complexity when a binary search tree is formed by inserting nodes in random input order?
It is O(logn)
In a binary search tree, what happens when you delete a node with only one child?
Set the parent node’s child pointer to the child of the deleted node (Splice out the node).
Free the deleted node’s memory.
