Binary Trees Flashcards
types of trees
Ordered tree (implies rooted)
Binary tree (implies ordered)
m-ary tree (usually ordered)
Labeled and/or search tree
R-B Tree
AVL Tree
What does each node of a binary tree consist of?
• A value (some sort of data item) • A reference or pointer to a left child (may be null), and A reference or pointer to a right child (may be null)
If a binary tree is not empty it has a…?
root node
A node without a left or right child is called a…?
leaf
What is the order of a tree?
number of nodes
What is the size of a tree?
number of edges, order -1
What is the depth of a node?
distance from root to the node where root to root is depth of 0
What is the height of a tree?
depth of the deepest node
For the following what is the order, size, depth (from a⇒a, a⇒e, a⇒k) and height
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/824/949/q_image_thumb.jpg?1466282268)
order = 12
size = 11
depth = 0, 2, 3 respectively
height = 4
When is an m-ary tree balanced?
When the heights of the subtrees of every node never differ by more than one.
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/825/012/a_image_thumb.png?1466282621)
When is a m-ary tree full?
full if every node has either 0 or m children
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/825/106/a_image_thumb.jpg?1466282761)
When is a m-ary tree complete?
complete if all levels have no missing siblings/cousins, except possibly the last (partial left-filled) level
pre, post and in order
![](https://s3.amazonaws.com/brainscape-prod/system/cm/191/825/157/a_image_thumb.jpg?1466283024)
what is it called to o visit nodes from top-to-bottom and left-to-right
level-order traversal
Average height for BST, R-B tree and AVL trees?
BST: 4 lg n
R-B: 2 lg n
AVL: 1.5 lg n