# Binary Trees Flashcards

1
Q

types of trees

A

Ordered tree (implies rooted)

Binary tree (implies ordered)

m-ary tree (usually ordered)

Labeled and/or search tree

R-B Tree

AVL Tree

2
Q

What does each node of a binary tree consist of?

A

• 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)

3
Q

If a binary tree is not empty it has a…?

A

root node

4
Q

A node without a left or right child is called a…?

A

leaf

5
Q

What is the order of a tree?

A

number of nodes

6
Q

What is the size of a tree?

A

number of edges, order -1

7
Q

What is the depth of a node?

A

distance from root to the node where root to root is depth of 0

8
Q

What is the height of a tree?

A

depth of the deepest node

9
Q

For the following what is the order, size, depth (from a⇒a, a⇒e, a⇒k) and height

A

order = 12

size = 11

depth = 0, 2, 3 respectively

height = 4

10
Q

When is an m-ary tree balanced?

A

When the heights of the subtrees of every node never differ by more than one.

11
Q

When is a m-ary tree full?

A

full if every node has either 0 or m children

12
Q

When is a m-ary tree complete?

A

complete if all levels have no missing siblings/cousins, except possibly the last (partial left-filled) level

13
Q

pre, post and in order

A
14
Q

what is it called to o visit nodes from top-to-bottom and left-to-right

A

level-order traversal

15
Q

Average height for BST, R-B tree and AVL trees?

A

BST: 4 lg n

R-B: 2 lg n

AVL: 1.5 lg n

16
Q

What are B-Trees used for?

A

• A B-tree implements the table API but used for external/slow devices such as disks (or cloud)

17
Q

What is a B-Tree?

A

A B-tree of order m is an m-ary tree such that:

• the root is either a leaf or it has between 2 and m children;
• each nonleaf node (except possibly the root) has between

dm/2e and m children inclusive;

• each nonleaf node with µ children has µ − 1 keys;
• all leaves are at the same depth;
18
Q

What is a red-black tree?

A

A red-black tree is a binary search tree such that every node is colored either red or black and every non-leaf node has two children. In addition, it satisfies the following properties:

• the root is black;
• all children of a red node must be black;
• every path from the root node to a leaf must contain the same number of black nodes.
19
Q

If every path from the root to a leaf contains b black nodes then how many black nodes are in the tree?

A

at least 2b − 1 black nodes

20
Q

What is the height of an AVL tree with n nodes?

A

Θ(log n) (AVL trees are more rigidly balanced than red-black trees so good for applications with more prominent search-only operations)

21
Q

What technique is used to make sure worst case does not occur in BST?

A

balancing

22
Q

What is an AVL tree?

A

An AVL tree is a binary search tree with the additional balance property that the tree is balanced

23
Q

What is a BST?

A

A binary search tree (BST) is a binary tree that satisfies the following ordering relation: for every node ν in the tree, the values of all the keys in the left subtree are smaller than (or equal, if duplicates allowed) to the key in ν and the values of all the keys in the right subtree are greater than the key in ν.

Left subtree has smaller valued nodes then right subtree

24
Q

The search, retrieval, update, insert and remove operations in a BST all take what time?

A

O(h) in the worst case, where h is the height of the tree