HELLO! I have an assignment in Data Structures course regarding to trees. Please solve it step by step using pen and pap
Posted: Mon Jun 06, 2022 12:31 pm
HELLO! I have an assignment in Data Structures course regarding
to trees. Please solve it step by step using pen and paper, and
explaining the steps. Do not code.
Question : Discussion
○ Can a remove(x) operation increase the height of any node in a
Binary Search tree? If so,
by how much?
○ Can an add() operation increase the height of any node in a
BinarySearch Tree? Can it
increase the height of the tree? If so, by how much?
○ If we have some Binary Search Tree and perform the operations
add(x) followed by
remove(x) (with the same value of x) do we necessarily return to
the original tree?
○ If we have some AVL Tree and perform the operations add(x)
followed by remove(x)
(with the same value of x) do we necessarily return to the original
tree?
○ We start with a binary search tree, T, and delete x then y from
T, giving a tree, T0 .
Suppose instead, we delete first y then x from T. Do we get the
same tree T0? Give a
proof or a counterexample.
to trees. Please solve it step by step using pen and paper, and
explaining the steps. Do not code.
Question : Discussion
○ Can a remove(x) operation increase the height of any node in a
Binary Search tree? If so,
by how much?
○ Can an add() operation increase the height of any node in a
BinarySearch Tree? Can it
increase the height of the tree? If so, by how much?
○ If we have some Binary Search Tree and perform the operations
add(x) followed by
remove(x) (with the same value of x) do we necessarily return to
the original tree?
○ If we have some AVL Tree and perform the operations add(x)
followed by remove(x)
(with the same value of x) do we necessarily return to the original
tree?
○ We start with a binary search tree, T, and delete x then y from
T, giving a tree, T0 .
Suppose instead, we delete first y then x from T. Do we get the
same tree T0? Give a
proof or a counterexample.