Java之treeSet

末蓝、 2024-04-18 22:38 48阅读 0赞

### 文章目录 ###

*   *   *  一、底层数据结构
         *  二、方法思维导图
         *  三、部分源代码
         *   *  1.add(E e)
             *  2.Iterator

### 一、底层数据结构 ###

public TreeSet() {
            this(new TreeMap<E,Object>());
        }

该数据结构是基于**treeMap**实现的

### 二、方法思维导图 ###

略.

### 三、部分源代码 ###

#### 1.add(E e) ####

将参数放入二叉排序树中

// 部分方法源码
    
    // 查找插入的位置
    do {
         parent = t;  
         cmp = k.compareTo(t.key);
         if (cmp < 0)
              t = t.left;
          else if (cmp > 0)
              t = t.right;
          else
              return t.setValue(value); // key相同就设置其value
      } while (t != null);
    
    
    // 初始化节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;

将节点调整至符合红黑树的规则

x.color = RED;
    
          //插入节点的父节点为红节点
            while (x != null && x != root && x.parent.color == RED) {   
                if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {   //父节点是祖父节点的左节点
                    Entry<K,V> y = rightOf(parentOf(parentOf(x))); // 获取父节点的兄弟节点
                    if (colorOf(y) == RED) { //若父节点的兄弟节点存在并且颜色为红色
                        setColor(parentOf(x), BLACK); 
                        setColor(y, BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        x = parentOf(parentOf(x));  //祖父节点代表的子树已经设置ok, 将插入节点设置为祖父节点
                    } else { // 父节点的兄弟节点不存在
                        if (x == rightOf(parentOf(x))) { //如果插入节点位于父节点的右子节点
                            x = parentOf(x);
                            rotateLeft(x); // 根据父节点左旋
                        }
                        setColor(parentOf(x), BLACK); 
                        setColor(parentOf(parentOf(x)), RED);
                        rotateRight(parentOf(parentOf(x))); //根据祖父节点右旋
                    }
                } else { 
                    Entry<K,V> y = leftOf(parentOf(parentOf(x))); //判断是否有兄弟节点
                    if (colorOf(y) == RED) {
                        setColor(parentOf(x), BLACK);
                        setColor(y, BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        x = parentOf(parentOf(x));
                    } else {
                        if (x == leftOf(parentOf(x))) {
                            x = parentOf(x);
                            rotateRight(x);
                        }
                        setColor(parentOf(x), BLACK);
                        setColor(parentOf(parentOf(x)), RED);
                        rotateLeft(parentOf(parentOf(x)));
                    }
                }
            }
            root.color = BLACK; //设置根节点为黑色
        }

#### 2.Iterator ####

public Iterator<E> iterator() {
          if (m instanceof TreeMap)
               return ((TreeMap<E,Object>)m).keyIterator();
           else
               return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
       }

**进入keyIterator**,

Iterator<K> keyIterator() {
            return new KeyIterator(getFirstEntry()); //getFirstEntry() 获取最左边的节点, 
        }

**Go on**,

final class KeyIterator extends PrivateEntryIterator<K> {
            KeyIterator(Entry<K,V> first) {
                super(first);
            }
            public K next() {
                return nextEntry().key;
            }
        }

**这里可以看到是调用了父类PrivateEntryIterator进行初始化.**

next方法

public K next() {
           return nextEntry().key;
          }

**Go on,**

final Entry<K,V> nextEntry() {
                Entry<K,V> e = next;
                if (e == null)
                    throw new NoSuchElementException();
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                next = successor(e); // 获取当前返回节点的下一个节点
                lastReturned = e;
                return e;
            }

**successor方法就是中序遍历的一个实现**

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
            if (t == null)
                return null;
            else if (t.right != null) { //当前节点存在右子节点
                Entry<K,V> p = t.right;
                while (p.left != null)
                    p = p.left; // 找到最左边节点
                return p;
            } else { // 当前节点为叶子节点或没有右子节点
                Entry<K,V> p = t.parent;
                Entry<K,V> ch = t;
                while (p != null && ch == p.right) {
                    ch = p;
                    p = p.parent;
                }
                return p;
            }
        }

为什么第二个判断是`t.right != null`  
在初始化时已经调用`getFirstEntry()`获取左子树最左边子节点.**因此遍历从最左边的子节点开始**,只需要考虑是否存在右子节点即可.

最后一个else的判断`while (p != null && ch == p.right)`  
(1) 若**当前节点为父节点的右子节点**, 那么父节点以及当前节点已经遍历完成(右子节点总是最后遍历到啊)——当前子树已经遍历完成. 因此需要找到当前子树的父节点, 直到然后重新判断, **直到符合(2)的要求**或者**p.parent==null(说明已经遍历完成)**.  
(2) 若**当前节点为父节点的左子节点**, 那么下一个遍历的就是父节点, 因为左子节点总是最先遍历.

**中序遍历的顺序:** **左子节点——>根节点——>右子节点**

![在这里插入图片描述][20190915214059383.PNG]

[20190915214059383.PNG]: https://img-blog.csdnimg.cn/20190915214059383.PNG