Create BinarySearchTree with ceiling() method, more efficient than TreeSet in library!


  • 0
    H

    If we use TreeSet, its ceiling() method will finally call the getCeilingEntry() method in TreeMap class.

    But getCeilingEntry() method rollback to track the last element greater than the target value. That is not efficient enough.

    ```java
    final Entry<K,V> getCeilingEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else if (cmp > 0) {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.right) { // ROLLBACK FOR LAST ELEMENT GREATER THAN TARGET
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;
        }
        return null;
    }
    

    So if we spend a little while to write a new Binary Search Tree, that can optimize the performance. The following code runs 13ms, beats 97%.

    public class Solution {
        private static class TreeNode {
            private long val;
            private TreeNode left;
            private TreeNode right;
            private TreeNode(long n) { val = n; }
        }
        private static class BinarySearchTreeWithDummy {
    
            private TreeNode dummy = new TreeNode(0); // sentinel
    
            /** Insert new element into the tree
             *  Return true if new value is added
             *  Return false if this value is already exist
             */
            private boolean add(long n) {
                TreeNode pre = dummy, cur = dummy.right; // head is always the right child of dummy
                boolean fromLeft = false;
                while (cur != null) {
                    long val = cur.val;
                    if (val > n) { // go left
                        pre = cur; cur = cur.left; fromLeft = true;
                    } else if (val < n) { // go right
                        pre = cur; cur = cur.right;
                    } else { // value already exist
                        return false;
                    }
                }
                TreeNode newNode = new TreeNode(n);
                if (fromLeft) {
                    pre.left = newNode;
                } else {
                    pre.right = newNode;
                }
                return true;
            }
            /**
             * Return true if the target is removed
             * Return false if target doesn't exist
             */
            private boolean remove(long n) {
                TreeNode pre = dummy, cur = dummy.right;
                boolean fromLeft = false;
                while (cur != null) {
                    if (cur.val > n) { // go left
                        pre = cur; cur = cur.left; fromLeft = true;
                    } else if (cur.val < n) { // go right
                        pre = cur; cur = cur.right;
                    } else { // find target
                        TreeNode tempHead = new TreeNode(0);
                        if (cur.left != null) {
                            tempHead.left = cur.left;
                            tempHead.right = cur.right;
                            cur = cur.left;
                            while (cur.right != null) { cur = cur.right; }
                            cur.right = tempHead.right;
                        } else {
                            tempHead.left = cur.right;
                        }
                        if (fromLeft) {
                            pre.left = tempHead.left;
                        } else {
                            pre.right = tempHead.left;
                        }
                        return true;
                    }
                }
                return false;
            }
            /**
             * Return least element greater than the input n
             * Return null if there is no element greater than n
             */
            private Long ceiling(long n) {
                TreeNode lastGreater = null;
                TreeNode cur = dummy.right;
                while (cur != null) {
                    if (cur.val > n) { // go left
                        lastGreater = cur; cur = cur.left; // use lastGreater to mark the last element greater than target , thus we don't need to rollback when we reach the leaf of the tree.
                    } else if (cur.val < n) {
                        cur = cur.right;
                    } else { // find target
                        return new Long(cur.val);
                    }
                }
                return (lastGreater == null)? null : new Long(lastGreater.val);
            }
        }
        /**
         * Solution based on Binary Search Tree
         * Use my BinarySearchTreeWithDummy
         */
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (nums.length < 2) { return false; }
            if (t < 0) { return false; }
            BinarySearchTreeWithDummy tree = new BinarySearchTreeWithDummy();
            for (int slow = 0, fast = 0; fast < nums.length; fast++) {
                if (fast > k) { tree.remove((long)nums[slow++]); }
                long floor = (long)nums[fast] - t;
                long ceil = (long)nums[fast] + t;
                Long firstGreaterThanFloor = tree.ceiling(floor);
                if (firstGreaterThanFloor != null && firstGreaterThanFloor <= ceil) { return true; }
                tree.add((long)nums[fast]);
            }
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.