2
Informatik (Subject) / BinarySearchTree (Lesson)
- insert public void insert(ContentType pContent) { if (pContent != null) { if (isEmpty()) { this.node = new BSTNode<ContentType>(pContent); } else if (pContent.isLess(this.node.content)) { this.node.left.insert(pContent); } else if(pContent.isGreater(this.node.content)) { this.node.right.insert(pContent); } } }
- remove public void remove(ContentType pContent) { if (isEmpty()) { // Abbrechen, da kein Element zum entfernen vorhanden ist. return; } if (pContent.isLess(node.content)) { // Element ist im linken Teilbaum zu loeschen. node.left.remove(pContent); } else if (pContent.isGreater(node.content)) { // Element ist im rechten Teilbaum zu loeschen. node.right.remove(pContent); } else { // Element ist gefunden. if (node.left.isEmpty()) { if (node.right.isEmpty()) { // Es gibt keinen Nachfolger. node = null; } else { // Es gibt nur rechts einen Nachfolger. node = getNodeOfRightSuccessor(); } } else if (node.right.isEmpty()) { // Es gibt nur links einen Nachfolger. node = getNodeOfLeftSuccessor(); } else { // Es gibt links und rechts einen Nachfolger. if (getNodeOfRightSuccessor().left.isEmpty()) { // Der rechte Nachfolger hat keinen linken Nachfolger. node.content = getNodeOfRightSuccessor().content; node.right = getNodeOfRightSuccessor().right; } else { BinarySearchTree<ContentType> previous = node.right.ancestorOfSmallRight(); BinarySearchTree<ContentType> smallest = previous.node.left; this.node.content = smallest.node.content; previous.remove(smallest.node.content); } } } }