Difference between revisions of "TADM2E 5.32"
From Algorithm Wiki
(Redirected page to UNTV) |
|||
| 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): |
| + | |||
| + | # 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> | ||
Latest revision as of 00:51, 1 August 2020
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.
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)); } } }
