Untitled

mail@pastecode.io avatar
unknown
java
2 years ago
1.6 kB
3
Indexable
Never
    public static<K extends Comparable, E> E deleteNode(TNode<K, E> root, K key) {
        TNode<K, E> toDel = root, parent = root;
        E temp = null;
        while(toDel != null && toDel.getKey() != key) {
            parent = toDel;
            if(key.compareTo(toDel.getKey()) < 0) {
                toDel = toDel.getLeft();
            } else {
                toDel = toDel.getRight();
            }
        }
        
        if(toDel == null) {
            return null;
        } else {
            temp = toDel.getItem();
            deleteNode(toDel, parent);
        }
        return temp;
    }
    
    private static <K extends Comparable, E> void deleteNode(TNode<K, E> toDel, TNode<K, E> parent) {
        if(toDel == null) return;
        
        if(toDel.getRight() != null && toDel.getLeft() != null) {
            TNode<K, E> largest = toDel.getRight(), largestParent = toDel;
            while(largest != null && largest.getRight() != null) {
                largestParent = largest;
                largest = largest.getRight();
            }
            toDel.setItem(largest.getItem());
            toDel.setKey(largestParent.getKey());
            deleteNode(largest, largestParent);
        } else {
            TNode<K, E> child;
            if(toDel.getLeft() != null) {
                child = toDel.getLeft();
            } else {
                child = toDel.getRight();
            }
            
            if(parent.getLeft() == toDel) {
                parent.setLeft(child);
            } else {
                parent.setRight(child);
            }
            
        }
    }