Trees

Front 1

What is a red/ black tree?

Back 1

A balanced binary search tree such that:

-all nodes are either red or black

-root is black

-leaves all point to null

-all nulls are black (same as root)

-all red nodes have at only black children (0-2)

Front 2

What's a critical property of red/black trees?

Back 2

The path from the root to the furthest leaf is no more than twice the length of the path from the root to the closest leaf,

Front 3

What is the average case time complexity to access a red/black tree?

Back 3

O(log(n))

Front 4

What is the worst case time complexity to access a red/black tree

Back 4

O(log(n))

Front 5

What is the average case time complexity to search a red/black tree

Back 5

O(log(n))

Front 6

What's the worst case time complexity to search a red/black tree?

Back 6

O(log(n))

Front 7

What's the average case time complexity to insert into a red/black tree?

Back 7

O(log(n))

Front 8

What's the worst case time complexity to insert into a red/black tree?

Back 8

O(log(n))

Front 9

What's the average case time complexity to delete from a red/black tree?

Back 9

O(log(n))

Front 10

What's the worst case time complexity to delete from a red/black tree?

Back 10

O(log(n))

Front 11

What's the worst case space complexity?

Back 11

O(n)

Front 12

What's a left-leaning red/black tree?

Back 12

A red black tree such that:

-If a node is red, it is the left child of it's parent

-on any root-null path, no more than two consecutive nodes are red

-all root-null paths have same number of black nodes

Front 13

what's an n-ary tree?

Back 13

A tree where every parent has at most n children

Front 14

How do you contruct a tree?

Back 14

nodes with a link to parent and links to any/all children

Front 15

What's bfs?

Back 15

Breadth first search. Explores all of the nodes at height k before moving to nodes at height k+1

Front 16

What's dfs?

Back 16

Depth first search. Explores all of the nodes on a root-null path, maintaining maximum height k at every choice.

Front 17

What's inorder?

Back 17

When doing depth first search, you first traverse the left subtree by recursively calling the in-order function, then display the data of the root, then traverse the right subtree by recursively calling the in-order function

Front 18

What's preorder?

Back 18

When doing depth first search you display the root first, then traverse the left subtree recursively calling pre-order, then traverse the right subtree recursively calling pre-order

Front 19

What's postorder

Back 19

When doing depth first search you traverse the left subtree recursively calling post order, then the right subtree recursively calling post order, then display the data of the root element.

Front 20

What is a splay tree?

Back 20

A binary tree such that nodes that are accessed frequently are near the root, because every time a node is accessed the splay operation is called

Front 21

What is avl tree

Back 21

A binary tree such that the heights of the two child subtrees of any node differ by at most one.

Front 22

What is trie tree?

Back 22

It's a tree that stores the prefix of the current value in the parent. For exameple.

t

r h

e y e

e

Front 23

What's the result for right rotate on a binary search tree:

------------y-

------x--------gamma

alpha beta

Back 23

result should be

-------------x-

-------alpha -y-

------------beta gamma

Front 24

Write some pseudo code for left rotate on a bst

-------------x-

-------alpha -y-

------------beta gamma

Back 24

y = x.right

x.right = y.left

if y.left != NULL, y.left.p = x

y.p = x.p

if x.p == NULL, T.root = y

elseif x == x.p.left, x.p.left = y

else x.p.right = y

y.left = x

x.p = y

Front 25

What's the result for left rotate on a BST

-------------x-

-------alpha -y-

------------beta gamma

Back 25

------------y-

------x--------gamma

alpha beta

Front 26

Write some pseudo code for right rotate on a bst

------------y-

------x--------gamma

alpha beta

Back 26

x = y.left

y.left = x.right

if x.right != NULL, x.right.p = y

x.p = y.p

if y.p == NULL, T.root = x

elseif y == y.p.right, y.p.right = x

else y.p.left = x

x.right = y

y.p = x

Front 27

Write some pseudo code to insert into a r/b bst

Back 27

insert(T,z)

y = T.nil

x = T.root

While x != T.nill

y = x

if z.key < x.ky, x = x.left

else x = x.right

z.p = y

if y == T.nil, T.root = z

elseif z.key < y.key, y.left = z

else y.right = z

z.left = T.nil

z.right = T.nil

z.color = red

Insert-Fixup(T, z)

Front 28

Write some pseudo-code to fix the results of insert on a r/b tree

Back 28

While x.p.color == red

if z.p == z.p.p.left,

y = z.p.p.right

if y. color == red

z..color = black

y.color = black

z.p.p.color = red

z = z.p.p

elseif z = z.p.right

z = z.p

left-rotate(T,z)

z.p.color = black

z.p.p.color = red

else (same as above ith right and left exchanged)

T.root..color = black

Front 29

Write some pseudo-code to delete from a r/b tree

Back 29

need to add

Front 30

What's the difference between a bst and a heap?

Back 30

In a max heap, the root is the max value and any children are less than that (opposite for a min-heap); in a bst, the left child is less than the shared parent is less than the right child.