TADM2E 5.32 - Revision history

Matt: Undo revision 1083 by FuckMatt (talk)

2020-08-01T00:51:58Z

Undo revision 1083 by FuckMatt (talk)

FuckMatt: Redirected page to UNTV

2020-07-31T10:12:50Z

Redirected page to UNTV

Matt: Undo revision 834 by Ufsuraifs (talk)

2020-07-23T14:46:01Z

Undo revision 834 by Ufsuraifs (talk)

Ufsuraifs: Replaced content with "Eat bulaga!"

2020-07-17T02:50:32Z

Replaced content with "Eat bulaga!"

Blazedaces: Created page with "Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. Ther..."

2017-01-29T09:00:33Z

Created page with "Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. Ther..."

New page

Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. There are 3 cases (I am assuming the index is 0-based):

# index is equal to the left tree's size => This value is the ith node in sorted order
# index is less than the left tree's size => The ith node is in the left tree
# index is greater than the left tree's size + 1 => The ith node is in the right tree

The implementation below only defines the methods required to answer this question, but clearly a full implementation of a binary search tree would need to have more.

<source lang="java">
import java.util.Optional;

public class BinarySearchTree {
private Optional<BinarySearchTree> left;
private Optional<BinarySearchTree> right;
private int value;
private int size;

public BinarySearchTree(final int value, final Optional<BinarySearchTree> left, final Optional<BinarySearchTree> right) {
this.value = value;
this.left = left;
this.right = right;
this.size = getLeftSize() + getRightSize() + 1;
}

private Integer getRightSize() {
return this.right.map(r -> r.size).orElse(0);
}

private Integer getLeftSize() {
return this.left.map(l -> l.size).orElse(0);
}

public int findIthNodeInSortedOrder(final int index) {
if (index < 0) {
throw new ArrayIndexOutOfBoundsException("Index cannot be less than 0");
}

if (index >= size) {
throw new ArrayIndexOutOfBoundsException("Index cannot be greater than or equal to size");
}

if (index == getLeftSize()) {
return value;
} else if (index < getLeftSize()) {
return left.get().findIthNodeInSortedOrder(index);
} else {
return right.get().findIthNodeInSortedOrder(index - (getLeftSize() + 1));
}
}
}
</source>

← Older revision		Revision as of 10:12, 31 July 2020
Line 1:		Line 1:
−	Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. There are 3 cases (I am assuming the index is 0-based):	+	#REDIRECT [[UNTV]]
−
−	# ~~index is equal to the left tree's size => This value is the ith node in sorted order~~
−	~~# index is less than the left tree's size => The ith node is in the left tree~~
−	~~# index is greater than the left tree's size + 1 => The ith node is in the right tree~~
−
−	~~The implementation below only defines the methods required to answer this question, but clearly a full implementation of a binary search tree would need to have more.~~
−
−	~~<source lang="java">~~
−	~~import java.util.Optional;~~
−
−	~~public class BinarySearchTree {~~
−	~~private Optional<BinarySearchTree> left;~~
−	~~private Optional<BinarySearchTree> right;~~
−	~~private int value;~~
−	~~private int size;~~
−
−	~~public BinarySearchTree(final int value, final Optional<BinarySearchTree> left, final Optional<BinarySearchTree> right) {~~
−	~~this.value = value;~~
−	~~this.left = left;~~
−	~~this.right = right;~~
−	~~this.size = getLeftSize() + getRightSize() + 1;~~
−	}
−
−	~~private Integer getRightSize() {~~
−	~~return this.right.map(r -> r.size).orElse(0);~~
−	}
−
−	~~private Integer getLeftSize() {~~
−	~~return this.left.map(l -> l.size).orElse(0);~~
−	}
−
−	~~public int findIthNodeInSortedOrder(final int index) {~~
−	~~if (index < 0) {~~
−	~~throw new ArrayIndexOutOfBoundsException("Index cannot be less than 0");~~
−	}
−
−	~~if (index >= size) {~~
−	~~throw new ArrayIndexOutOfBoundsException("Index cannot be greater than or equal to size");~~
−	}
−
−	~~if (index == getLeftSize()) {~~
−	~~return value;~~
−	~~} else if (index < getLeftSize()) {~~
−	~~return left.get().findIthNodeInSortedOrder(index);~~
−	~~} else {~~
−	~~return right.get().findIthNodeInSortedOrder(index - (getLeftSize() + 1));~~
−	}
−	}
−	}
−	~~</source>~~

← Older revision		Revision as of 02:50, 17 July 2020
Line 1:		Line 1:
−	Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. There are 3 cases (I am assuming the index is 0-based):	+	Eat bulaga!
−
−	~~# index is equal to the left tree's size => This value is the ith node in sorted order~~
−	~~# index is less than the left tree's size => The ith node is in the left tree~~
−	~~# index is greater than the left tree's size + 1 => The ith node is in the right tree~~
−
−	~~The implementation below only defines the methods required to answer this question, but clearly a full implementation of a binary search tree would need to have more.~~
−
−	~~<source lang="java">~~
−	~~import java.util.Optional;~~
−
−	~~public class BinarySearchTree {~~
−	~~private Optional<BinarySearchTree> left;~~
−	~~private Optional<BinarySearchTree> right;~~
−	~~private int value;~~
−	~~private int size;~~
−
−	~~public BinarySearchTree(final int value, final Optional<BinarySearchTree> left, final Optional<BinarySearchTree> right) {~~
−	~~this.value = value;~~
−	~~this.left = left;~~
−	~~this.right = right;~~
−	~~this.size = getLeftSize() + getRightSize() + 1;~~
−	}
−
−	~~private Integer getRightSize() {~~
−	~~return this.right.map(r -> r.size).orElse(0);~~
−	}
−
−	~~private Integer getLeftSize() {~~
−	~~return this.left.map(l -> l.size).orElse(0);~~
−	}
−
−	~~public int findIthNodeInSortedOrder(final int index) {~~
−	~~if (index < 0) {~~
−	~~throw new ArrayIndexOutOfBoundsException("Index cannot be less than 0");~~
−	}
−
−	~~if (index >= size) {~~
−	~~throw new ArrayIndexOutOfBoundsException("Index cannot be greater than or equal to size");~~
−	}
−
−	~~if (index == getLeftSize()) {~~
−	~~return value;~~
−	~~} else if (index < getLeftSize()) {~~
−	~~return left.get().findIthNodeInSortedOrder(index);~~
−	~~} else {~~
−	~~return right.get().findIthNodeInSortedOrder(index - (getLeftSize() + 1));~~
−	}
−	}
−	}
−	~~</source>~~

← Older revision		Revision as of 00:51, 1 August 2020
Line 1:		Line 1:
−	#~~REDIRECT [[UNTV]]~~	+	Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. There are 3 cases (I am assuming the index is 0-based):
		+
		+	# index is equal to the left tree's size => This value is the ith node in sorted order
		+	# index is less than the left tree's size => The ith node is in the left tree
		+	# index is greater than the left tree's size + 1 => The ith node is in the right tree
		+
		+	The implementation below only defines the methods required to answer this question, but clearly a full implementation of a binary search tree would need to have more.
		+
		+	<source lang="java">
		+	import java.util.Optional;
		+
		+	public class BinarySearchTree {
		+	private Optional<BinarySearchTree> left;
		+	private Optional<BinarySearchTree> right;
		+	private int value;
		+	private int size;
		+
		+	public BinarySearchTree(final int value, final Optional<BinarySearchTree> left, final Optional<BinarySearchTree> right) {
		+	this.value = value;
		+	this.left = left;
		+	this.right = right;
		+	this.size = getLeftSize() + getRightSize() + 1;
		+	}
		+
		+	private Integer getRightSize() {
		+	return this.right.map(r -> r.size).orElse(0);
		+	}
		+
		+	private Integer getLeftSize() {
		+	return this.left.map(l -> l.size).orElse(0);
		+	}
		+
		+	public int findIthNodeInSortedOrder(final int index) {
		+	if (index < 0) {
		+	throw new ArrayIndexOutOfBoundsException("Index cannot be less than 0");
		+	}
		+
		+	if (index >= size) {
		+	throw new ArrayIndexOutOfBoundsException("Index cannot be greater than or equal to size");
		+	}
		+
		+	if (index == getLeftSize()) {
		+	return value;
		+	} else if (index < getLeftSize()) {
		+	return left.get().findIthNodeInSortedOrder(index);
		+	} else {
		+	return right.get().findIthNodeInSortedOrder(index - (getLeftSize() + 1));
		+	}
		+	}
		+	}
		+	</source>

← Older revision		Revision as of 14:46, 23 July 2020
Line 1:		Line 1:
−	~~Eat bulaga!~~	+	Assuming our binary search tree keeps track of its size we can write a recursive function which checks whether the index is in the left tree, the right, or is this value. There are 3 cases (I am assuming the index is 0-based):
		+
		+	# index is equal to the left tree's size => This value is the ith node in sorted order
		+	# index is less than the left tree's size => The ith node is in the left tree
		+	# index is greater than the left tree's size + 1 => The ith node is in the right tree
		+
		+	The implementation below only defines the methods required to answer this question, but clearly a full implementation of a binary search tree would need to have more.
		+
		+	<source lang="java">
		+	import java.util.Optional;
		+
		+	public class BinarySearchTree {
		+	private Optional<BinarySearchTree> left;
		+	private Optional<BinarySearchTree> right;
		+	private int value;
		+	private int size;
		+
		+	public BinarySearchTree(final int value, final Optional<BinarySearchTree> left, final Optional<BinarySearchTree> right) {
		+	this.value = value;
		+	this.left = left;
		+	this.right = right;
		+	this.size = getLeftSize() + getRightSize() + 1;
		+	}
		+
		+	private Integer getRightSize() {
		+	return this.right.map(r -> r.size).orElse(0);
		+	}
		+
		+	private Integer getLeftSize() {
		+	return this.left.map(l -> l.size).orElse(0);
		+	}
		+
		+	public int findIthNodeInSortedOrder(final int index) {
		+	if (index < 0) {
		+	throw new ArrayIndexOutOfBoundsException("Index cannot be less than 0");
		+	}
		+
		+	if (index >= size) {
		+	throw new ArrayIndexOutOfBoundsException("Index cannot be greater than or equal to size");
		+	}
		+
		+	if (index == getLeftSize()) {
		+	return value;
		+	} else if (index < getLeftSize()) {
		+	return left.get().findIthNodeInSortedOrder(index);
		+	} else {
		+	return right.get().findIthNodeInSortedOrder(index - (getLeftSize() + 1));
		+	}
		+	}
		+	}
		+	</source>