摘要：知識(shí)點(diǎn)總結(jié)容器知識(shí)點(diǎn)總結(jié)容器是接口的唯一實(shí)現(xiàn)，可以確保集合元素處于排序狀態(tài)，底層是一棵排序樹(shù)。底層使用紅黑樹(shù)算法進(jìn)行維護(hù)，因此性能相對(duì)于來(lái)說(shuō)要差一些，因?yàn)閮?nèi)部會(huì)自動(dòng)進(jìn)行排序操作。

@(Java知識(shí)點(diǎn)總結(jié))[Java, Java容器, JavaCollection, JavaSet]

TreeSet是SortedSet接口的唯一實(shí)現(xiàn)，TreeSet可以確保集合元素處于排序狀態(tài)，底層是一棵排序樹(shù)。

底層使用紅黑樹(shù)算法進(jìn)行維護(hù)，因此性能相對(duì)于HashSet來(lái)說(shuō)要差一些，因?yàn)閮?nèi)部會(huì)自動(dòng)進(jìn)行排序操作。

TreeSet也是線程不安全

排序分為自然排序，定制排序，自然排序是TreeSet內(nèi)部對(duì)add進(jìn)來(lái)的值進(jìn)行排序，定制排序是對(duì)排序條件的限制

package mySet;  
  
import java.util.Comparator;  
import java.util.Iterator;  
import java.util.NoSuchElementException;  
  
/** 
 * 實(shí)現(xiàn)一個(gè)簡(jiǎn)單的TreeSet 
 * @author george 
 */  
public class MyTreeSet implements Cloneable, java.io.Serializable {  
    // 為set底層樹(shù)的結(jié)構(gòu)排序用的比較器 當(dāng)按照E的自然排序時(shí)為null  
    private final Comparator comparator;  
    // 頭節(jié)點(diǎn)  
    private transient SetNode root = null;  
    // 節(jié)點(diǎn)個(gè)數(shù)  
    private transient int size = 0;  
  
    /** 
     * 無(wú)參構(gòu)造，設(shè)置比較器為null 
     */  
    public MyTreeSet() {  
        comparator = null;  
    }  
  
    /** 
     * 構(gòu)造函數(shù)，傳入定義好的比較器對(duì)象 
     *  
     * @param comparator 
     *            ：比較器對(duì)象 
     */  
    public MyTreeSet(Comparator comparator) {  
        this.comparator = comparator;  
    }  
  
    /** 
     * 插入對(duì)象e到MyTreeSet中 
     *  
     * @param e 
     *            ：要插入的對(duì)象 
     * @return：返回是否插入成功 
     */  
    public boolean add(E e) {  
        SetNode n = root;  
        if (n == null) {  
            root = new SetNode(e, null);  
            size = 1;  
            return true;  
        }  
        int comp;  
        SetNode parents;  
        Comparator cptor = comparator;  
        // 若比較器不為空 用Comparator進(jìn)行比較  
        if (cptor != null) {  
            do {  
                parents = n;  
                comp = cptor.compare(e, n.e);  
                if (comp < 0)  
                    n = n.left;  
                else if (comp > 0)  
                    n = n.right;  
                else {  
                    return false;  
                }  
            } while (n != null);  
        } else {  
            if (e == null)  
                throw new NullPointerException();  
            // 用定義好的自然順序方法進(jìn)行排序比較  
            Comparable cpb = (Comparable) e;  
            do {  
                parents = n;  
                comp = cpb.compareTo(n.e);  
                if (comp < 0)  
                    n = n.left;  
                else if (comp > 0)  
                    n = n.right;  
                else {  
                    return false;  
                }  
            } while (n != null);  
        }  
        // 找到新元素將來(lái)位置的父結(jié)點(diǎn)后，將元素實(shí)例化成結(jié)點(diǎn)插入到樹(shù)中  
        SetNode newNode = new SetNode(e, parents);  
        if (comp < 0)  
            parents.left = newNode;  
        else  
            parents.right = newNode;  
        size++;  
        return true;  
    }  
  
    /** 
     * 返回是否含有元素e 
     *  
     * @param e 
     * @return 
     */  
    public boolean contains(E e) {  
        return getNode(e) != null;  
    }  
  
    /** 
     * 刪除元素e所在的結(jié)點(diǎn) 
     *  
     * @param e 
     * @return 
     */  
    public boolean remove(E e) {  
        SetNode node = getNode(e);// 找到元素e所在節(jié)點(diǎn)  
        if (node == null)  
            return false;  
        deleteNode(node);// 進(jìn)行刪除  
        return true;  
    }  
  
    /** 
     * 找到元素e在樹(shù)中的結(jié)點(diǎn) 
     *  
     * @param e 
     * @return 
     */  
    private SetNode getNode(E e) {  
        SetNode n = root;  
        int comp;  
        SetNode parents;  
        Comparator cptor = comparator;  
        // 若比較器不為空 用Comparator進(jìn)行比較  
        if (cptor != null) {  
            do {  
                parents = n;  
                comp = cptor.compare(e, n.e);  
                if (comp < 0)  
                    n = n.left;  
                else if (comp > 0)  
                    n = n.right;  
                else {  
                    return parents;  
                }  
            } while (n != null);  
        } else {  
            if (e == null)  
                throw new NullPointerException();  
            // 用定義好的自然順序方法進(jìn)行排序比較  
            Comparable cpb = (Comparable) e;  
            do {  
                parents = n;  
                comp = cpb.compareTo(n.e);  
                if (comp < 0)  
                    n = n.left;  
                else if (comp > 0)  
                    n = n.right;  
                else {  
                    return parents;  
                }  
            } while (n != null);  
        }  
        return null;  
    }  
  
    /** 
     * 刪除樹(shù)中的節(jié)點(diǎn)node 當(dāng)結(jié)點(diǎn)node有左右子女時(shí)，往下所搜與node中的元素最為接近的元素的結(jié)點(diǎn) 
     * 找到后將該結(jié)點(diǎn)的元素值賦給node，讓node指向該結(jié)點(diǎn)， 接下來(lái)刪除這個(gè)結(jié)點(diǎn)。 注意：最后要去掉的節(jié)點(diǎn)的子女個(gè)數(shù)都是小于2的 
     *  
     * @param node 
     */  
    void deleteNode(SetNode node) {  
        size--;  
        SetNode rep;  
        if (node.left != null && node.right != null) {  
            rep = replaceNode(node);  
            node.e = rep.e;  
            node = rep;  
        }  
        rep = (node.left != null ? node.left : node.right);  
  
        if (rep != null) {  
            rep.parents = node.parents;  
            if (node.parents == null)  
                root = rep;  
            else if (node == node.parents.left)  
                node.parents.left = rep;  
            else if (node == node.parents.right)  
                node.parents.right = rep;  
        } else {  
            if (node.parents == null) {  
                root = null;  
            }  
            if (node.parents != null) {  
                if (node == node.parents.left)  
                    node.parents.left = null;  
                else if (node == node.parents.right)  
                    node.parents.right = null;  
            }  
        }  
    }  
  
    /** 
     * 找到距離node中的元素大小最近的結(jié)點(diǎn) 
     *  
     * @param node 
     * @return 
     */  
    SetNode replaceNode(SetNode node) {  
        if (node == null)  
            return null;  
        else if (node.right != null) {  
            SetNode p = node.right;  
            while (p.left != null)  
                p = p.left;  
            return p;  
        } else {  
            SetNode p = node.parents;  
            SetNode ch = node;  
            while (p != null && ch == p.right) {  
                ch = p;  
                p = p.parents;  
            }  
            return p;  
        }  
    }  
  
    /** 
     * 清空set集合 
     */  
    public void clear() {  
        size = 0;  
        root = null;  
    }  
  
    /** 
     * 返回結(jié)點(diǎn)的個(gè)數(shù) 
     *  
     * @return 
     */  
    public int size() {  
        return size;  
    }  
  
    /** 
     * 找到最小的元素 
     *  
     * @return 
     */  
    public E first() {  
        SetNode p = root;  
        if (p != null)  
            while (p.left != null)  
                p = p.left;  
        if (p.e == null)  
            throw new NoSuchElementException();  
        else  
            return p.e;  
    }  
  
    /** 
     * 找到最大的元素 
     *  
     * @return 
     */  
    public E last() {  
        SetNode p = root;  
        if (p != null)  
            while (p.right != null)  
                p = p.right;  
        if (p.e == null)  
            throw new NoSuchElementException();  
        else  
            return p.e;  
    }  
  
    /** 
     * 找到最小的元素所在的結(jié)點(diǎn) 
     *  
     * @return 
     */  
    public SetNode firstNode() {  
        SetNode p = root;  
        if (p != null)  
            while (p.left != null)  
                p = p.left;  
        if (p.e == null)  
            throw new NoSuchElementException();  
        else  
            return p;  
    }  
  
    /** 
     * 迭代器 
     * @return 
     */  
    public Iterator iterator() {  
        return new KeyIterator(firstNode(), this);  
    }  
}