Trees

Question 1

What is a full binary tree?

Answer 1

a tree in which every node has either 0 or 2 children

Question 2

what is a complete binary tree?

Answer 2

every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Question 3

perfect binary tree?

Answer 3

is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level

Question 4

Is a tree that is full and complete necessarily perfect?

Answer 4

NO. You could still have have missing nodes on the right side of the last level (but where all interior levels have no missing nodes (fulfilling the complete property)), but where the second to last level is entirely composed of nodes that have either 0 or 2 children (fulfilling the full property) the

Question 5

pre order, in order, vs post order

Answer 5

refers to when you visit the root node;
pre order visits root, left, then right
in order visits left, root, right
post order visits left, right, root

Question 6

What happens when items are inserted into a BST in sorted key order?

Answer 6

The tree degenerates into a linked list with n nodes

Question 7

How to prevent BSTs from degenerating into linked lists?

Answer 7

Use self balancing binary search trees

Question 8

Name 7 implementations of self balancing binary search trees

Answer 8

2-3 tree, AVL tree, B-tree, red black tree, splay tree, scapegoat tree, tango tree

Question 9

What is the differentiating concept between splay trees and other self balancing binary search trees?

Answer 9

Splay trees allow for faster access of recently accessed elements. When an operation is being performed on an element, the tree performs an operation called splaying which pulls the element to the top of the tree

Question 10

Ben Pfaff paper

Answer 10

Compares performance of different self balancing BST implementations

Regular BSTs excel when randomly ordered input can be relied upon (input as in insertions, accesses, or both?).

Splay trees excel when data is often inserted in a sorted order and later accesses are sequential ( I think author means accessing data in the sorted order it was inserted) or clustered. ( I think author means like repeated access of the same element)

AVL trees excel when data is often inserted in a sorted order and later accesses are random.

Red-black trees excel when data is often inserted in random order but occasional runs of sorted order are expected. [ what about frequent runs of sorted order??] [ by runs does it mean insertions or accesses??]
[what about deletions?]

Question 11

When are red-black trees preferred over AVL trees?

Answer 11

when there is high frequency of insert/delete operations compared to search as AVL tree balancing (rotation) is expensive. AVL trees are useful if lookup (search) is a lot more common than insertion/deletion.

Question 12

why do red-black trees have faster insertions/deletions than AVL trees?

Answer 12

they have less strict rules around rebalancing. Conversely, AVL tree is more strictly balanced so lookups are faster than RB tree.

Question 13

etymology of trie

Answer 13

derived from the word retrieval. pronounced “try”

Question 14

Performance of self balancing binary trees vs binary heaps

Answer 14

In practice self balancing binary trees are slower. This has to do with the fact that heaps can be implemented on top of an array, while BSTs use recursive tree data structures with child pointers. Array has much better locality of reference.

Question 15

Binomial tree

Answer 15

Always has 2^N nodes for some integer N

Not sure yet of the structure, but it deinfitely doesn’t always have <=2 children on each node like a binary tree . E.g sometimes has 3 nodes

Question 16

What is the ratio of insert+deletes to search at which at or greater than this ratio R-b trees are more performant than AVL trees?

Answer 16

[not sure. But see Ben pfaff paper or other papers]

Question 17

If self balancing trees are slower than binary heaps in practice, then when are do self balancing trees have any use cases in the real world?

Answer 17

…

Question 18

When would we use self balancing bsts for a priority queue instead of a binary heap?

Answer 18

According to geeks for geeks, we would use it for a doubly ended priority queue:

With a Binary Heap, we can either implement a priority queue with support of extractMin() or with extractMax(). If we wish to support both the operations, we use a Self-Balancing Binary Search Tree to do both in O(Log n)

Question 19

Worst case height of AVL tree

Answer 19

~1.44 log(n)

Question 20

Worst case height of RB tree

Answer 20

2 log n