edu.princeton.cs.algs4.growingtree.interfaces
Interface IDeletingNode<P extends NodeProperties>

Type Parameters:

P -

All Superinterfaces:

java.lang.Comparable<INode<P>>, IAlgorithmNode<P>, INode<P>

All Known Implementing Classes:

ShadowNode

public interface IDeletingNode<P extends NodeProperties>
extends IAlgorithmNode<P>

This interface is used by IDeleteOperator to delete a node.

Author:

Josh Israel

See Also:

IDeleteOperator

Method Summary

IAlgorithmNode<P>	predecessorHibbardDelete() Identical to successorHibbardDelete, except swaps with predecessor.
IAlgorithmNode<P>	successorHibbardDelete() This performs Hibbard deletion.

Methods inherited from interface edu.princeton.cs.algs4.growingtree.interfaces.IAlgorithmNode

freeze, freeze, getLeft, getParent, getPredecessor, getRight, getRoot, getSuccessor, rotateLeft, rotateRight

Methods inherited from interface edu.princeton.cs.algs4.growingtree.interfaces.INode

getLogger, getNodeProperties

Methods inherited from interface java.lang.Comparable

compareTo

Method Detail

successorHibbardDelete

IAlgorithmNode<P> successorHibbardDelete()

This performs Hibbard deletion. There are 3 cases: If the node is a leaf, it is simply removed. If the node has 1 child, it is replaced by its child If the node has 2 children, it is swapped with its successor and then deleted as a node with 1 child or a leaf.

Returns:

If a leaf, null. If it has 1 child, returns its child. If it has 2 children, the child of the successor.

predecessorHibbardDelete

IAlgorithmNode<P> predecessorHibbardDelete()

Identical to successorHibbardDelete, except swaps with predecessor.

Returns:

If a leaf, null. If it has 1 child, returns its child. If it has 2 children, the child of the predecessor.