Binärer Suchbaum delete

[Unit]

Habe ein Problem mit der delete-Methode eines Binärbaumes. Es Klappt alles ganz gut nur die 3. Bedingung (Knoten mit 2 Kindern) macht mir noch Probleme kann mir da jemand helfen? Das Problem liegt darin, dass wenn der Successor selbst im Unterbaum liegt der an den Successor dran gehängt wird.

    public void delete(T data)

    {

        BNode<T> dNode = find(data);



        if (dNode == root)

        {

            if (root.getChildCount() > 0)

            {

                getSuccessor(root).setLeftChild(root.getLeftChild());

                root = getSuccessor(root);

            } else

            {

                root = null;

            }

        } else

        {



            BNode<T> parent = getParent(dNode);

            if (dNode.isLeaf())

            {



                if (parent.getLeftChild() == dNode)

                {

                    parent.setLeftChild(null);

                } else if (parent.getRightChild() == dNode)

                {

                    parent.setRightChild(null);

                }

            } else if (dNode.getChildCount() == 1)

            {

                if (dNode.getLeftChild() != null)

                {

                    if (getParent(dNode).getRightChild() == dNode)

                    {

                        getParent(dNode).setRightChild(dNode.getLeftChild());

                    } else if (getParent(dNode).getLeftChild() == dNode)

                    {

                        getParent(dNode).setLeftChild(dNode.getLeftChild());

                    }

                } else if (dNode.getRightChild() != null)

                {

                    if (getParent(dNode).getRightChild() == dNode)

                    {

                        getParent(dNode).setRightChild(dNode.getRightChild());

                    } else if (getParent(dNode).getLeftChild() == dNode)

                    {

                        getParent(dNode).setLeftChild(dNode.getRightChild());

                    }

                }

            } else if (dNode.getChildCount() == 2)

            {

                BNode<T> successor = getSuccessor(dNode);

                if (successor != null)

                {



                    if (getParent(dNode).getRightChild() == dNode)

                    {

                        successor.setLeftChild(dNode.getLeftChild());

                        successor.setRightChild(dNode.getRightChild());

                        getParent(dNode).setRightChild(successor);



                    } else if (getParent(dNode).getLeftChild() == dNode)

                    {

                        successor.setRightChild(dNode.getRightChild());

                        successor.setLeftChild(dNode.getLeftChild());

                        getParent(dNode).setLeftChild(successor);

                    }

                }

            }

        }

    }

 

[Bitfehler]

Moin,

Annahme: Knoten K hat zwei Kinder und soll gelöscht werden
Mögliches Vorgehen:

1. Bestimme Vorgänger-Knoten V
2. Merke dir den ersten Knoten R des rechten Teilbaums
3. Hänge den linken Teilbaum (K.getLeftChild) an den Vorgänger-Knoten V(entweder rechts oder links)
4. Hänge den gemerkten Knoten R nach unten in den linken Teilbaum

Dieses Verfahren erzeugt (hoffentlich) einen Baum, der allerdings nicht besonders gut ausbalanciert ist. Es gibt ein weiteres Verfahren, dass beim Löschen eines Knotens einen besser balancierten Baum erzeugt (Siehe: https://de.wikipedia.org/wiki/Binärbaum#L.C3.B6schen)

Schönen Abend noch