title: DSA-As-2
date: 2023-10-15
author: AllenYGY
status: DONE
created: 2024-01-15T23:44
updated: 2024-06-11T01:14
publish: TrueDSA-As-2
Problem I
GETSUM(A, left, right)
IF left > right
return 0
center = left + (right - left) / 2
if(A[center] == 0 AND center + 1 < A.size AND A[center + 1] == 1)
return A.size - center - 1
else if(A[center] == 1)
return GETSUM(A, left, center - 1)
else
return GETSUM(A, center + 1, right)
When
Problem II
- initial state:
- |1|3|6|5|4|7|
- insert(1)
- |1|3|6|5|4|7|
- insert(3)
- |3|1|6|5|4|7|
- insert(6)
- |6|1|3|5|4|7|
- insert(5)
- |6|5|3|1|4|7|
- insert(4)
- |6|5|3|1|4|7|
- insert(7)
- |7|5|6|1|4|3|
- deleteMax()
- |6|5|3|1|4|7|
- deleteMax()
- |5|4|3|1|6|7|
- deleteMax()
- |4|1|3|5|6|7|
- deleteMax()
- |3|1|4|5|6|7|
- deleteMax()
- |1|3|4|5|6|7|
Problem III
isBST(node, lower, upper)
IF node IS NULL
RETURN TRUE
IF node.key <= lower OR node.key >= upper
RETURN FALSE
RETURN isBST(node.left, lower, node.key) AND isBST(node.right, node.key, upper)
isBST(root, INT_MIN, INT_MAX)
Problem IV
initial state:
25|3
┌───────────────┴───────────────┐
13|1 80|2
┌───────┴───────┐ ┌───────┴───────┐
6|0 15|0 58|1 82|0
└───┐
65|0
insert:29
25|3
┌───────────────┴───────────────┐
13|1 80|2
┌───────┴───────┐ ┌───────┴───────┐
6|0 15|0 58|1 82|0
┌───┴───┐
29|0 65|0
insert:70
25|3
┌───────────────┴───────────────┐
13|1 65|2
┌───────┴───────┐ ┌───────┴───────┐
6|0 15|0 58|1 80|1
┌───┘ ┌───┴───┐
29|0 70|0 82|0
insert:68
65|3
┌───────────────┴───────────────┐
25|2 80|2
┌───────┴───────┐ ┌───────┴───────┐
13|1 58|1 70|1 82|0
┌───┴───┐ ┌───┘ ┌───┘
6|0 15|0 29|0 68|0
Problem V
a)
b)
Table Of Contents