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
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.
When is a m-ary tree full?
full if every node has either 0 or m children
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
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
What are B-Trees used for?
• A B-tree implements the table API but used for external/slow devices such as disks (or cloud)
What is a B-Tree?
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;
What is a red-black tree?
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.
If every path from the root to a leaf contains b black nodes then how many black nodes are in the tree?
at least 2b − 1 black nodes
What is the height of an AVL tree with n nodes?
Θ(log n) (AVL trees are more rigidly balanced than red-black trees so good for applications with more prominent search-only operations)
What technique is used to make sure worst case does not occur in BST?
balancing
What is an AVL tree?
An AVL tree is a binary search tree with the additional balance property that the tree is balanced
What is a BST?
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
The search, retrieval, update, insert and remove operations in a BST all take what time?
O(h) in the worst case, where h is the height of the tree
