一、ceiling操作

1、ceilingEntry函數(shù)

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的最小結(jié)點
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        // 如果大于，一直向右查找，如果右邊為空了，則向上找到第一個左父結(jié)點
       } 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函數(shù)返回的是大于等于指定key的最小結(jié)點，不存在的話返回空

2、ceilingKey函數(shù)

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函數(shù)返回的是大于等于指定key的最小結(jié)點的key，不存在的話返回空

二、floor操作

1、floorEntry函數(shù)

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，向右查找，如果右節(jié)點為空，那么當(dāng)前被比較的結(jié)點就是要找的結(jié)點
        if (cmp > 0) {
            if (p.right != null)
                p = p.right;
            else
                return p;
        // 小于0，向左查找，如果左節(jié)點為空，那么向上找，找的第一個右父結(jié)點就是要找的結(jié)點
       } 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的結(jié)點最大結(jié)點，沒有則返回空

2、floorKey函數(shù)

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的結(jié)點最大結(jié)點的key，沒有則返回空

三、higher操作

1、higherEntry函數(shù)

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函數(shù)返回大于指定key的最小結(jié)點，如果不存在返回空

四、lower操作

1、lowerEntry函數(shù)

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函數(shù)小于指定key的最大的結(jié)點，如果沒有返回空