源码篇-TreeMap之Floor与Ceiling操作

一、ceiling操作

1、ceilingEntry函数

public Map.Entry<K,V> ceilingEntry(K key) {
    return exportEntry(getCeilingEntry(key));
}

final Entry<K,V> getCeilingEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.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) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        // 如果等于直接返回
       } else
            return p;
    }
    return null;
}   

• ceilingEntry函数返回的是大于等于指定key的最小结点，不存在的话返回空

2、ceilingKey函数

public K ceilingKey(K key) {
    return keyOrNull(getCeilingEntry(key));
}

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) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;
    }
    return null;
}   

• ceilingKey函数返回的是大于等于指定key的最小结点的key，不存在的话返回空

二、floor操作

1、floorEntry函数

public Map.Entry<K,V> floorEntry(K key) {
    return exportEntry(getFloorEntry(key));
}

final Entry<K,V> getFloorEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        // 大于0，向右查找，如果右节点为空，那么当前被比较的结点就是要找的结点
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        // 小于0，向左查找，如果左节点为空，那么向上找，找的第一个右父结点就是要找的结点
       } else if (cmp < 0) {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        // 如果等于直接返回
       } else
            return p;

    }
    return null;
}   
    

• floorEntry返回小于等于指定key的结点最大结点，没有则返回空

2、floorKey函数

public K floorKey(K key) {
    return keyOrNull(getFloorEntry(key));
}
final Entry<K,V> getFloorEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else if (cmp < 0) {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;

    }
    return null;
}   

• floorKey返回小于等于指定key的结点最大结点的key，没有则返回空

三、higher操作

1、higherEntry函数

public Map.Entry<K,V> higherEntry(K key) {
    return exportEntry(getHigherEntry(key));
}
final Entry<K,V> getHigherEntry(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 (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}   

• higherEntry函数返回大于指定key的最小结点，如果不存在返回空

四、lower操作

1、lowerEntry函数

public Map.Entry<K,V> lowerEntry(K key) {
    return exportEntry(getLowerEntry(key));
}

final Entry<K,V> getLowerEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        } else {
            if (p.left != null) {
                p = p.left;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.left) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}   

• lowerEntry函数小于指定key的最大的结点，如果没有返回空