TreeMap排序源码分析有疑问

直接上代码

public V put(K key, V value) {//插入或设置元素,返回原始value值(如果插入返回null)  
        Entry<K,V> t = root;  
        if (t == null) {//根元素为空时直接建立根元素  
        // TBD:  
        // 5045147: (coll) Adding null to an empty TreeSet should  
        // throw NullPointerException  
        //  
        // compare(key, key); // type check  
            root = new Entry<K,V>(key, value, null);  
            size = 1;  
            modCount++;  
            return null;  
        }  
        int cmp;  
        Entry<K,V> parent;  
        // split comparator and comparable paths  
        Comparator<? super K> cpr = comparator;  
        if (cpr != null) {//存在比较器  
            do {//循环查找父元素  
                parent = t;//设置父元素  
                cmp = cpr.compare(key, t.key);  
                if (cmp < 0)  
                    t = t.left;//继续查找左边元素  
                else if (cmp > 0)  
                    t = t.right;//继续查找右边元素  
                else  
                    return t.setValue(value);//相等直接进行value设置  
            } while (t != null);  
        }  
        else {//不存在比较器,按compareTo方法查找  
            if (key == null)  
                throw new NullPointerException();  
            Comparable<? super K> k = (Comparable<? super K>) key;  
            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);  
            } while (t != null);  
        }  
        Entry<K,V> e = new Entry<K,V>(key, value, parent);  
        if (cmp < 0)  
            parent.left = e;  
        else  
            parent.right = e;  
        fixAfterInsertion(e);  
        size++;  
        modCount++;  
        return null;  
    }  

疑问点在于,

if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);

上面这段代码的意思是,根据比较器想t移到原来节点的子节点。那么移动以后parent节点是原来的t,t变到了原来的子节点,那么下面这段代码又是什么意思呢。

if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);

让parent的左右节点成e(插入节点),那么岂不是跟t节点重复了?t阶段存在的意义到底是什么。

4个回答

if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
如果比较是小于,然后插入左边,否则插入右边
t节点是原来的,e是插入的。先要搬动原来的节点,然后再插入e。
最后fixAfterInsertion(e); 调整二叉树使平衡。

StackTc
StackTc 每次都赋值了。谢谢了。可以说一下 fixAfterInsertion 这个方法的主要作用吗
大约 2 年之前 回复
StackTc
StackTc 回复StackTc: 我懂了,parent、
大约 2 年之前 回复
StackTc
StackTc parent = t; 这一步将赋值给parent,第一次赋值的时候由于t是根节点,所以parent也是根节点,但是随着t的移动为什么parent变成了t的父节点? 有点理解不了,按照我的理解是parent应该永远是根节点
大约 2 年之前 回复

treemap使用了二叉排序树来实现有序的存储,在二叉排序树中,任何一个节点都比它的左子节点大,比右子节点小。而每次插入都要将新的节点放入其中,并且重新调整构成平衡二叉树。

具体的算法可以google或者看数据结构的书。

StackTc
StackTc 二叉树我懂,但是我上面的疑问可以解释下吗
大约 2 年之前 回复

第一段代码所在的do-while循环是用来查找元素e应该在二叉树的哪个位置,具体可以看二分查找法。
第二段代码是确定元素e是在前面查出来的节点的左边还是右边。

StackTc
StackTc 第一段的t在第二段根本没用到。
大约 2 年之前 回复

parent = t; 这一步将赋值给parent,第一次赋值的时候由于t是根节点,所以parent也是根节点,但是随着t的移动为什么parent变成了t的父节点?
有点理解不了,按照我的理解是parent应该永远是根节点。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问