Как я могу оптимизировать это двоичное дерево поиска?

Я добавил несколько методов в базовую реализацию BST для целых чисел — если кто-нибудь может указать, как это можно было бы написать более эффективно или чисто, дайте мне знать.

public class BST {
    
    /*
     *  1) Node inner class
     */
    
    private class Node {
        
        int data;
        Node leftChild, rightChild;
        
        public Node(int num, Node left, Node right) {
            this.data = num;
            this.leftChild = left;
            this.rightChild = right;
        }

    }
    
    
    // 2) Variables
    
    private Node root = null;   // every binary search tree object will be assigned a root node = null
    private int nodeCount = 0;
    
    // 3) Methods: size
    public int size() {
        return nodeCount;
    }
    
    // 4) Methods: isEmpty
    public boolean isEmpty() {
        return (root == null);   // if the root of the BST is null (we haven't added any nodes) then the BST is empty
    }
    
    // 5) Methods: contains (recursive), SEARCH
    public boolean treeContains(int info) {
        return treeContains(root, info);
    }
    
    public boolean treeContains(Node node, int info) {
        
        if (node == null) return false;   // corner case: if tree is null, but also BASE CASE
        
        // SEARCHING, but looking for a number so we can use O log(n) time
        if (info > node.data) { // go to the right
            return treeContains(node.rightChild, info);
            }
        else if (info < node.data) {
            return treeContains(node.leftChild, info);
        }
        else {  // either node has bigger or smaller data or this case: it is equal
            return true;
        }
    }
    
    // 6) Methods: add
    public boolean add(int newData) {
        if (treeContains(newData)) return false;
        
        else {
            root = add(root, newData);  // NOTE: this works but why can't it just be add(root,newdata) without the "root = " ?
            nodeCount++;
            return true;    
        }
    }
    
    public Node add(Node node, int newData) {
        
        if (node == null) {
            node = new Node(newData, null, null);               // NOTE: how does this add a node? it doesn't place it anywhere? it just exists somewhere? i mean i understand that by then we're pointing to a space that is null but still
        }
        
        else if (newData > node.data) {
            node.rightChild = add(node.rightChild, newData);
            }
        else {                                                  // else if newData is less or equal to node data
            node.leftChild = add(node.leftChild, newData);
            }
        return node;
    }
    
    // 7) Methods: remove
    // look up node to be removed, set it to null, recursive
    
    public boolean remove(int newData) {
        if (!treeContains(newData)) return false;  // will null BST's fall under this ???
        
        else {
            root = remove(root,newData);        // NOTE: why do we need to have root = remove(root, newData) ??? instead of just remove..
            nodeCount--;
            return true;
        }
    }
    
    public Node remove(Node node, int newData) {
        
        if (node.data == newData) {         // if we find the node we want to delete 
            
            // 3 SCENARIOS - the node can be a leaf, can have 1 or 2 children
            
            // leaf node
            if (node.leftChild==null && node.rightChild== null) {
                node = null;
            }
            
            // node has left child only
            else if (node.leftChild !=null && node.rightChild == null) {
                node.data = node.leftChild.data;   // left child is now node
                node.leftChild = null;
            }
            
            // node has right child only
            else if (node.leftChild==null && node.rightChild!=null) {
                Node temp = node.rightChild;        // trying another way of switching nodes & deleting
                node.rightChild = null;
                node.data = temp.data; 
            }
            
            // node has both children
            else {
                Node temp = findMin(node.rightChild);       
                node.data = temp.data;                          // switch data
                node.rightChild = remove(node.rightChild, temp.data);   // remove the findMin node, originally node.RC = remove...
            }
        }
        
        else if (newData < node.data) {
            node.leftChild = remove (node.leftChild, newData);
        }
        
        else {   // if newData > node.data
            node.rightChild = remove(node.rightChild, newData);
        }
        
        return node;
    }
    
      // Helper method to find the leftmost node (which has the smallest value)
      private Node findMin(Node node) {
        while (node.leftChild != null) 
            node = node.leftChild;
        return node;
      }

    
    
    // 8) Methods: In order tree traversal
      public void traverseInOrder(Node node) {
          if (node == null) return;
          
          traverseInOrder(node.leftChild);
          System.out.print(node.data + " ");
          traverseInOrder(node.rightChild);
      }
    

    // 9) Methods: Pre order tree traversal
      public void traversePreOrder(Node node) {
          if (node == null) return;
          
          System.out.print(node.data + " ");
          traversePreOrder(node.leftChild);
          traversePreOrder(node.rightChild);
      }
    
    
    // 10) Methods: Post order tree traversal
      public void traversePostOrder(Node node) {
          if (node == null) return;
          
          traversePostOrder(node.leftChild);
          traversePostOrder(node.rightChild);
          System.out.print(node.data + " ");
      }
    

    // RUN METHODS
      
    public static void main(String[] args) {
        
        BST tree1 = new BST();
        
        tree1.add(10);
        tree1.add(7);
        tree1.add(5);
        tree1.add(8);
        tree1.add(20);
        tree1.add(15);
        tree1.add(25);
        
        tree1.traverseInOrder(tree1.root);
        
        System.out.println( "nSize of tree is: " + tree1.size() );
        System.out.println( "Root of tree is: " + tree1.root.data );
        System.out.println( "Min num of tree is: " + tree1.findMin(tree1.root).data );
        System.out.println( "Does the tree contain the #5 ? " + tree1.treeContains(5) );
        
        tree1.remove(8);
        tree1.remove(20);
        
        tree1.traverseInOrder(tree1.root);
        System.out.println( "nSize of tree is: " + tree1.size() );
    }
    

}

Спасибо!!

Я не разработчик Java, поэтому отнеситесь к обзору с недоверием.

Есть много лишних комментариев:

3) Methods: size

4) Methods: isEmpty

Мы уже можем видеть, что это метод и как он называется, посмотрев на код. Добавление строки документации для таких коротких методов необязательно.

public Node(int num, Node left, Node right) {
    this.data = num;
    ...
}

Почему аргумент назван num, но назначен data? Позже в коде вы вызываете num в виде newData, что более уместно.

if (treeContains(newData)) return false;
    else {
        root = add(root, newData);
        nodeCount++;
        return true;    
    }

Мне это кажется очень неудобным, и я бы переписал его так:

if (treeContains(newData)) return false;

root = add(root, newData);
nodeCount++;
return true;

// NOTE: this works but why can't it just be add(root,newdata) without the "root = " ?

Это потому что root, определенный как экземпляр класса private Node root = null обновляется

else if (node.leftChild !=null && node.rightChild == null)

else if (node.leftChild==null && node.rightChild!=null)

Интервалы повсюду. Предпочитайте пробелы вокруг оператора равенства. Например, node.leftChild == null

System.out.println( "Root of tree is: " + tree1.root.data );

Должны быть созданы новые общедоступные методы (getRoot() а также getValue()) для инкапсуляции.

public boolean add(int newData)

Сигнатура метода мне кажется странной. Что означает boolean что возвращается? (добавить в документацию)

Почему нельзя использовать узлы с одинаковым значением?

nodeCount++;

nodeCount--;

В этом случае не имеет большого значения, используется ли пре- или пост-инкремент / декремент. Если старое значение не имеет значения, следует использовать предварительное приращение.

    if (!treeContains(newData)) return false;  // will null BST's fall under this ???
    
    else {

Пожалуйста, не делай этого. Это больно читать и может вызвать ошибки, поскольку разделение else от if делает так, что вполне возможно, что if находится на одном экране, а else не на дне. Люди знают, что нужно проверить else на следующей строке. Заставлять нас продолжать проверять прошлое — это жестоко.

В этом случае это тоже не нужно. Вы возвращаетесь из первоначального предложения. Таким образом, остальная часть метода будет запущена только в случае неудачной проверки. Следовательно, вам не нужно использовать else вообще. Только if достаточно.

Как правило, старайтесь избегать смешивания форм операторов и блоков в одной и той же структуре управления. Это излишне увеличивает когнитивную нагрузку, когда кто-то читает код. И вообще, люди больше читают код, чем пишут. Потому что большая часть разработки заключается в изменении существующего кода, а не в написании нового кода.

Существует мнение, что вы никогда не должны использовать форму оператора структур управления, поскольку это приводит к ряду возможностей для странных, трудно обнаруживаемых ошибок. Например, сравните

    if (!treeContains(newData)) //return false;

    doSomething();

к

    if (!treeContains(newData)) {
        //return false;
    }

    doSomething();

На первый взгляд может показаться, что они делают то же самое. Но на самом деле они совсем другие. В частности, если doSomething имеет важные побочные эффекты.