Difference between revisions of "TADM2E 5.32"

From Algorithm Wiki
Jump to: navigation, search
(Replaced content with "Eat bulaga!")
(Undo revision 834 by Ufsuraifs (talk))
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>

Revision as of 14:46, 23 July 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):

  1. index is equal to the left tree's size => This value is the ith node in sorted order
  2. index is less than the left tree's size => The ith node is in the left tree
  3. 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));
        }
    }
}