Untitled

mail@pastecode.io avatar
unknown
java
2 years ago
2.2 kB
6
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 {
            if(parent.getLeft() == toDel) {
                if(toDel.isLeaf()) {
                    parent.setLeft(null);
                } else {
                    if(toDel.getLeft() != null) {
                        parent.setLeft(toDel.getLeft());
                        deleteNode(toDel.getLeft(), toDel);
                    } else {
                        parent.setLeft(toDel.getRight());
                        deleteNode(toDel.getRight(), toDel);
                    }
                }
            } else {
                if(toDel.isLeaf()) {
                    parent.setRight(null);
                } else {
                    if(toDel.getLeft() != null) {
                        parent.setRight(toDel.getLeft());
                        deleteNode(toDel.getLeft(), toDel);
                    } else {
                        parent.setRight(toDel.getRight());
                        deleteNode(toDel.getRight(), toDel);
                    }
                }
            }
        }
    }