реализация бинарного дерева поиска и Java

Question

Я пытаюсь реализовать алгоритм BST, используя псевдокод Кормена, но у меня проблема.

Вот мой код для узла:

public class Node {
    Node left;
    Node right;
    int value;

    Node(int value){
        this.value = value;
        this.left = null;
        this.right = null;  
    }
}

и для Bstree:

public class Btree {
    Node root;

    Btree(){
        this.root = null;
    }

    public static void inorderWalk(Node n){
        if(n != null){
            inorderWalk(n.left);
            System.out.print(n.value + " ");
            inorderWalk(n.right);
        }
    }

    public static Node getParent(Btree t, Node n){
        Node current = t.root;
        Node parent = null;


        while(true){
            if (current == null)
                return null;

            if( current.value == n.value ){
                break;
            }

            if (current.value > n.value){
                parent = current;
                current = current.left;
            }
            else{ //(current.value < n.value)
                parent = current;
                current = current.right;
            }       
        }
        return parent;
    }


    public static Node search(Node n,int key){
        if(n == null || key == n.value ){
            return n;
        }
        if(key < n.value){
            return search(n.left,key);
        }
        else{
            return search(n.right,key);

        }
    }

    public static Node treeMinimum(Node x){
        if(x == null){
            return null;
        }


        while(x.left != null){
            x = x.left;
        }
        return x;
    }

    public static Node treeMaximum(Node x){
        if(x == null){
            return null;
        }

        while(x.right != null){
            x = x.right;
        }
        return x;   
    }

    public static Node treeSuccessor(Btree t,Node x){
        if (x.right == null){
            return treeMinimum(x.right);
        }
        Node y = getParent(t,x);
        while(y != null && x == y.right){
            x = y;
            y = getParent(t,y);
        }
        return y;   
    }

    public static Btree insert(Btree t,Node z){
        Node y = null;
        Node x = t.root;

        while(x != null){
            y = x;
            if(z.value < x.value)
                x = x.left;
            else
                x = x.right;
        }
        Node tmp = getParent(t,z);
        tmp = y;
        if(y == null){
            t.root = z;
        }
        else if(z.value < y.value)
            y.left = z;
        else
            y.right = z;

        return t;
    }


    public static Btree delete(Btree t,Node z){
        Node y,x;
        if (z.left == null || z.right == null)
            y = z;
        else
            y = treeSuccessor(t,z);

        if (y.left != null)
            x = y.left;
        else
            x = y.right;
        if (x != null){
            Node tmp = getParent(t,x);
            tmp = getParent(t,y);
        }

        if (getParent(t,y) == null ){
            t.root = x;
        }
        else{
            if( y == getParent(t,y).left ){
                getParent(t,y).left = x;
            }
            else{
                getParent(t,y).right = x;

            }
    }
        if(y != z){
            z.value = y.value;
        }
    return t;
}

public static void main(String[] args){
    Btree test = new Btree(); 
    Node n1 = new Node(6);
    Node n2 = new Node(3);
    Node n3 = new Node(9);
    Node n4 = new Node(1);
    Node n5 = new Node(16);
    Node n6 = new Node(4);
    Node n7 = new Node(2);
    Node n8 = new Node(11);
    Node n9 = new Node(13);


    test = insert(test,n1);
    test = insert(test,n2);
    test = insert(test,n3);
    test = insert(test,n4);
    test = insert(test,n5);
    test = insert(test,n6);
    test = insert(test,n7);
    test = insert(test,n8);
    test = insert(test,n9);
    inorderWalk(test.root);
    System.out.println();
    test = delete(test,n8);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n5);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n2);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n1);
    inorderWalk(test.root);




}

}

Основная проблема связана с частью удаления, иногда она работает как задумано, иногда ошибочно удаляет, а иногда исключение нулевого указателя. В чем может быть проблема?

Ps: это НЕ домашнее задание

Answer 1

Некоторые проблемы с вашим кодом: ваш treeSuccessor начинается с

    if (x.right == null){
        return treeMinimum(x.right);
    }

что должно быть if (x.right != null), конечно.

Ваш код insert имеет строки

    Node tmp = getParent(t,z);
    tmp = y;

, где вы назначаете tmp и немедленно назначаете его снова. Мне не кажется, что вам нужны эти строки вообще, так как вы не используете tmp в дальнейшем. В этот момент у вас есть y узел, в чей дочерний элемент вставляется z, поэтому просто удалите эти строки.

Опять же, в delete у вас есть строки

    if (x != null){
        Node tmp = getParent(t,x);
        tmp = getParent(t,y);
    }

, где вы на самом деле ничего не делаете, поскольку tmp не виден вне этого фрагмента. И далее, в delete вы повторяете выражение getParent(t,y), которое может быть дорогостоящей операцией, поэтому вы должны вычислить его только один раз и присвоить его некоторой переменной.

Но в целом ваш код, хотя он и кажется правильным (возможно, кроме delete, который я не совсем понял, но который выглядит подозрительно), мало похож на типичный двоичный код дерева. Вам на самом деле не нужны методы getParent и treeSuccessor для реализации search, insert и delete. Базовая структура, которая у вас есть для search, работает и для других, со следующими модификациями:

• с insert, когда вы получаете ссылку null вместо возврата null, вставьте элемент в эту точку
• с delete, когда вы найдете элемент, если у него есть только один (или нет) дочерний элемент, замените его на этот дочерний элемент, и, если у него есть два дочерних элемента, замените его либо максимумом левого дочернего дерева, либо минимум правильного дочернего дерева

Оба из них требуют, кроме того, чтобы вы отслеживали родительский узел при спуске в дерево, но это единственное изменение, которое вам нужно внести в search. В частности, никогда не нужно подниматься вверх по дереву (что сделает treeSuccessor).

Answer 2

Прежде всего, ваша реализация не имеет никакого отношения к объектной ориентации (кроме использования объектов). Например, операции вставки и удаления должны работать с деревом.

Кроме того, я бы рекомендовал реализовать класс Node как статический член класса Tree.

public class Tree {
    private Node root = null;

    // remainder omitted

    public boolean insert(int element) {
        if (isEmpty()) {
            root = new Node(element);

            return true; // empty tree, Node could be inserted, return true
        }

         Node current = root; // start at root
         Node parent;         // the current Node's parent

         do {
             parent = current;

             if (element < current.element) {
                 current = current.left; // go to left
             } else if (element > current.element) {
                 current = current.right; // go to right
             } else {
                 return false;  // duplicates are NOT allowed, element could not be inserted -> return false

         } while (current != null);

         Node node = new Node(element);

         if (element < current.element) {
             parent.left = node;
         } else {
             parent.right = node;
         }

         return true; // node successfully inserted
    }

    public boolean isEmpty() {
        return root == null;
    }

    private static class Node { // static member class
        Node left  = null;
        Node right = null;
        final int element;

        Node(int element) {
            this.element = element;
        }
    }
}

Answer 3

... что случилось с вашим кодом удаления? Это не имеет большого смысла. Я бы подумал переписать его более логичным образом. Без бессмысленных однобуквенных имен переменных. И добавьте комментарии!

Один из возможных алгоритмов:

Get the parent of the node to delete
Get the right-most node of the left subtree, or the leftmost node of the right subtree
Remove the node to delete and replace it with the node you found
Rebalance the tree

... или, если вы хотите взломать этот материал, чтобы он был прав, я бы начал смотреть на

if (x != null){
    Node tmp = getParent(t,x);
    tmp = getParent(t,y);
}

часть, потому что это явно неправильно.

Answer 4

Вот полная реализация дерева двоичного поиска в Java вставка, поиск, countNodes, обход, удаление, пустой, максимальный и минимальный узел, поиск родительского узла, печать всех листовых узлов, получение уровня, получение высоты, получение глубины, печать в левом виде, зеркальное отображение

import java.util.NoSuchElementException;
import java.util.Scanner;

import org.junit.experimental.max.MaxCore;

class BSTNode {

    BSTNode left = null;
    BSTNode rigth = null;
    int data = 0;

    public BSTNode() {
        super();
    }

    public BSTNode(int data) {
        this.left = null;
        this.rigth = null;
        this.data = data;
    }

    @Override
    public String toString() {
        return "BSTNode [left=" + left + ", rigth=" + rigth + ", data=" + data + "]";
    }

}


class BinarySearchTree {

    BSTNode root = null;

    public BinarySearchTree() {

    }

    public void insert(int data) {
        BSTNode node = new BSTNode(data);
        if (root == null) {
            root = node;
            return;
        }

        BSTNode currentNode = root;
        BSTNode parentNode = null;

        while (true) {
            parentNode = currentNode;
            if (currentNode.data == data)
                throw new IllegalArgumentException("Duplicates nodes note allowed in Binary Search Tree");

            if (currentNode.data > data) {
                currentNode = currentNode.left;
                if (currentNode == null) {
                    parentNode.left = node;
                    return;
                }
            } else {
                currentNode = currentNode.rigth;
                if (currentNode == null) {
                    parentNode.rigth = node;
                    return;
                }
            }
        }
    }

    public int countNodes() {
        return countNodes(root);
    }

    private int countNodes(BSTNode node) {
        if (node == null) {
            return 0;
        } else {
            int count = 1;
            count += countNodes(node.left);
            count += countNodes(node.rigth);
            return count;
        }
    }

    public boolean searchNode(int data) {
        if (empty())
            return empty();
        return searchNode(data, root);
    }

    public boolean searchNode(int data, BSTNode node) {
        if (node != null) {
            if (node.data == data)
                return true;
            else if (node.data > data)
                return searchNode(data, node.left);
            else if (node.data < data)
                return searchNode(data, node.rigth);
        }
        return false;
    }

    public boolean delete(int data) {
        if (empty())
            throw new NoSuchElementException("Tree is Empty");

        BSTNode currentNode = root;
        BSTNode parentNode = root;
        boolean isLeftChild = false;

        while (currentNode.data != data) {
            parentNode = currentNode;
            if (currentNode.data > data) {
                isLeftChild = true;
                currentNode = currentNode.left;
            } else if (currentNode.data < data) {
                isLeftChild = false;
                currentNode = currentNode.rigth;
            }
            if (currentNode == null)
                return false;
        }

        // CASE 1: node with no child
        if (currentNode.left == null && currentNode.rigth == null) {
            if (currentNode == root)
                root = null;
            if (isLeftChild)
                parentNode.left = null;
            else
                parentNode.rigth = null;
        }

        // CASE 2: if node with only one child
        else if (currentNode.left != null && currentNode.rigth == null) {
            if (root == currentNode) {
                root = currentNode.left;
            }
            if (isLeftChild)
                parentNode.left = currentNode.left;
            else
                parentNode.rigth = currentNode.left;
        } else if (currentNode.rigth != null && currentNode.left == null) {
            if (root == currentNode)
                root = currentNode.rigth;
            if (isLeftChild)
                parentNode.left = currentNode.rigth;
            else
                parentNode.rigth = currentNode.rigth;
        }

        // CASE 3: node with two child
        else if (currentNode.left != null && currentNode.rigth != null) {

            // Now we have to find minimum element in rigth sub tree
            // that is called successor
            BSTNode successor = getSuccessor(currentNode);
            if (currentNode == root)
                root = successor;
            if (isLeftChild)
                parentNode.left = successor;
            else
                parentNode.rigth = successor;
            successor.left = currentNode.left;
        }

        return true;
    }

    private BSTNode getSuccessor(BSTNode deleteNode) {

        BSTNode successor = null;
        BSTNode parentSuccessor = null;
        BSTNode currentNode = deleteNode.left;

        while (currentNode != null) {
            parentSuccessor = successor;
            successor = currentNode;
            currentNode = currentNode.left;
        }

        if (successor != deleteNode.rigth) {
            parentSuccessor.left = successor.left;
            successor.rigth = deleteNode.rigth;
        }

        return successor;
    }

    public int nodeWithMinimumValue() {
        return nodeWithMinimumValue(root);
    }

    private int nodeWithMinimumValue(BSTNode node) {
        if (node.left != null)
            return nodeWithMinimumValue(node.left);
        return node.data;
    }

    public int nodewithMaximumValue() {
        return nodewithMaximumValue(root);
    }

    private int nodewithMaximumValue(BSTNode node) {
        if (node.rigth != null)
            return nodewithMaximumValue(node.rigth);
        return node.data;
    }

    public int parent(int data) {
        return parent(root, data);
    }

    private int parent(BSTNode node, int data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        if (root.data == data)
            throw new IllegalArgumentException("No Parent node found");

        BSTNode parent = null;
        BSTNode current = node;

        while (current.data != data) {
            parent = current;
            if (current.data > data)
                current = current.left;
            else
                current = current.rigth;
            if (current == null)
                throw new IllegalArgumentException(data + " is not a node in tree");
        }
        return parent.data;
    }

    public int sibling(int data) {
        return sibling(root, data);
    }

    private int sibling(BSTNode node, int data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        if (root.data == data)
            throw new IllegalArgumentException("No Parent node found");

        BSTNode cureent = node;
        BSTNode parent = null;
        boolean isLeft = false;

        while (cureent.data != data) {
            parent = cureent;
            if (cureent.data > data) {
                cureent = cureent.left;
                isLeft = true;
            } else {
                cureent = cureent.rigth;
                isLeft = false;
            }
            if (cureent == null)
                throw new IllegalArgumentException("No Parent node found");
        }
        if (isLeft) {
            if (parent.rigth != null) {
                return parent.rigth.data;
            } else
                throw new IllegalArgumentException("No Sibling is there");
        } else {
            if (parent.left != null)
                return parent.left.data;
            else
                throw new IllegalArgumentException("No Sibling is there");
        }
    }

    public void leafNodes() {
        if (empty())
            throw new IllegalArgumentException("Empty");
        leafNode(root);
    }

    private void leafNode(BSTNode node) {
        if (node == null)
            return;
        if (node.rigth == null && node.left == null)
            System.out.print(node.data + " ");
        leafNode(node.left);
        leafNode(node.rigth);
    }

    public int level(int data) {
        if (empty())
            throw new IllegalArgumentException("Empty");
        return level(root, data, 1);
    }

    private int level(BSTNode node, int data, int level) {
        if (node == null)
            return 0;
        if (node.data == data)
            return level;
        int result = level(node.left, data, level + 1);
        if (result != 0)
            return result;
        result = level(node.rigth, data, level + 1);
        return result;
    }

    public int depth() {
        return depth(root);
    }

    private int depth(BSTNode node) {
        if (node == null)
            return 0;
        else
            return 1 + Math.max(depth(node.left), depth(node.rigth));
    }

    public int height() {
        return height(root);
    }

    private int height(BSTNode node) {
        if (node == null)
            return 0;
        else
            return 1 + Math.max(height(node.left), height(node.rigth));
    }

    public void leftView() {
        leftView(root);
    }

    private void leftView(BSTNode node) {
        if (node == null)
            return;
        int height = height(node);

        for (int i = 1; i <= height; i++) {
            printLeftView(node, i);
        }
    }

    private boolean printLeftView(BSTNode node, int level) {
        if (node == null)
            return false;

        if (level == 1) {
            System.out.print(node.data + " ");
            return true;
        } else {
            boolean left = printLeftView(node.left, level - 1);
            if (left)
                return true;
            else
                return printLeftView(node.rigth, level - 1);
        }
    }

    public void mirroeView() {
        BSTNode node = mirroeView(root);
        preorder(node);
        System.out.println();
        inorder(node);
        System.out.println();
        postorder(node);
        System.out.println();
    }

    private BSTNode mirroeView(BSTNode node) {
        if (node == null || (node.left == null && node.rigth == null))
            return node;

        BSTNode temp = node.left;
        node.left = node.rigth;
        node.rigth = temp;

        mirroeView(node.left);
        mirroeView(node.rigth);
        return node;
    }

    public void preorder() {
        preorder(root);
    }

    private void preorder(BSTNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorder(node.left);
            preorder(node.rigth);
        }
    }

    public void inorder() {
        inorder(root);
    }

    private void inorder(BSTNode node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.data + " ");
            inorder(node.rigth);
        }
    }

    public void postorder() {
        postorder(root);
    }

    private void postorder(BSTNode node) {
        if (node != null) {
            postorder(node.left);
            postorder(node.rigth);
            System.out.print(node.data + " ");
        }
    }

    public boolean empty() {
        return root == null;
    }

}

public class BinarySearchTreeTest {
    public static void main(String[] l) {
        System.out.println("Weleome to Binary Search Tree");
        Scanner scanner = new Scanner(System.in);
        boolean yes = true;
        BinarySearchTree tree = new BinarySearchTree();
        do {
            System.out.println("\n1. Insert");
            System.out.println("2. Search Node");
            System.out.println("3. Count Node");
            System.out.println("4. Empty Status");
            System.out.println("5. Delete Node");
            System.out.println("6. Node with Minimum Value");
            System.out.println("7. Node with Maximum Value");
            System.out.println("8. Find Parent node");
            System.out.println("9. Count no of links");
            System.out.println("10. Get the sibling of any node");
            System.out.println("11. Print all the leaf node");
            System.out.println("12. Get the level of node");
            System.out.println("13. Depth of the tree");
            System.out.println("14. Height of Binary Tree");
            System.out.println("15. Left View");
            System.out.println("16. Mirror Image of Binary Tree");
            System.out.println("Enter Your Choice :: ");
            int choice = scanner.nextInt();
            switch (choice) {
            case 1:
                try {
                    System.out.println("Enter Value");
                    tree.insert(scanner.nextInt());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 2:
                System.out.println("Enter the node");
                System.out.println(tree.searchNode(scanner.nextInt()));
                break;

            case 3:
                System.out.println(tree.countNodes());
                break;

            case 4:
                System.out.println(tree.empty());
                break;

            case 5:
                try {
                    System.out.println("Enter the node");
                    System.out.println(tree.delete(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }

            case 6:
                try {
                    System.out.println(tree.nodeWithMinimumValue());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 7:
                try {
                    System.out.println(tree.nodewithMaximumValue());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 8:
                try {
                    System.out.println("Enter the node");
                    System.out.println(tree.parent(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 9:
                try {
                    System.out.println(tree.countNodes() - 1);
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 10:
                try {
                    System.out.println("Enter the node");
                    System.out.println(tree.sibling(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 11:
                try {
                    tree.leafNodes();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }

            case 12:
                try {
                    System.out.println("Enter the node");
                    System.out.println("Level is : " + tree.level(scanner.nextInt()));
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 13:
                try {
                    System.out.println(tree.depth());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 14:
                try {
                    System.out.println(tree.height());
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 15:
                try {
                    tree.leftView();
                    System.out.println();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            case 16:
                try {
                    tree.mirroeView();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
                break;

            default:
                break;
            }
            tree.preorder();
            System.out.println();
            tree.inorder();
            System.out.println();
            tree.postorder();
        } while (yes);
        scanner.close();
    }
}

Answer 5

Мне придется встать на сторону Анона и пойти на переписывание. Нулевые указатели приходят из вашей функции getParent (которая явно возвращает нули вместе с другими вещами) Поэтому я бы начал там и исправил функции, чтобы они возвращали одно и только одно в конце функции.