SHARE
TWEET

BinarySearchTree

LoganBlackisle Dec 6th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package binarysearchtreestuderende;
  2.  
  3. /**
  4.  * This class implements a binary search tree whose nodes hold objects that
  5.  * implement the Comparable interface.
  6.  */
  7. public class BinarySearchTree<E extends Comparable<E>> {
  8.     private Node root;
  9.  
  10.     /**
  11.      * Constructs an empty tree.
  12.      */
  13.     public BinarySearchTree() {
  14.         root = null;
  15.     }
  16.  
  17.     /**
  18.      * Inserts a new node into the tree.
  19.      *
  20.      * @param obj the object to insert
  21.      */
  22.     public void add(E obj) {
  23.         Node newNode = new Node();
  24.         newNode.data = obj;
  25.         newNode.left = null;
  26.         newNode.right = null;
  27.         if (root == null) {
  28.             root = newNode;
  29.         } else {
  30.             root.addNode(newNode);
  31.         }
  32.     }
  33.  
  34.     /**
  35.      * Tries to find an object in the tree.
  36.      *
  37.      * @param obj the object to find
  38.      * @return true if the object is contained in the tree
  39.      */
  40.     public boolean find(E obj) {
  41.         Node current = root;
  42.         boolean found = false;
  43.         while (!found && current != null) {
  44.             int d = current.data.compareTo(obj);
  45.             if (d == 0) {
  46.                 found = true;
  47.             } else if (d > 0) {
  48.                 current = current.left;
  49.             } else {
  50.                 current = current.right;
  51.             }
  52.         }
  53.         return found;
  54.     }
  55.  
  56.     /**
  57.      * Tries to remove an object from the tree. Does nothing if the object is not
  58.      * contained in the tree.
  59.      *
  60.      * @param obj the object to remove
  61.      */
  62.     public void remove(E obj) {
  63.         // Find node to be removed
  64.  
  65.         Node toBeRemoved = root;
  66.         Node parent = null;
  67.         boolean found = false;
  68.         while (!found && toBeRemoved != null) {
  69.             int d = toBeRemoved.data.compareTo(obj);
  70.             if (d == 0) {
  71.                 found = true;
  72.             } else {
  73.                 parent = toBeRemoved;
  74.                 if (d > 0) {
  75.                     toBeRemoved = toBeRemoved.left;
  76.                 } else {
  77.                     toBeRemoved = toBeRemoved.right;
  78.                 }
  79.             }
  80.         }
  81.  
  82.         if (found) {
  83.  
  84.             // toBeRemoved contains obj
  85.  
  86.             // If one of the children is empty, use the other
  87.  
  88.             if (toBeRemoved.left == null || toBeRemoved.right == null) {
  89.                 Node newChild;
  90.                 if (toBeRemoved.left == null) {
  91.                     newChild = toBeRemoved.right;
  92.                 } else {
  93.                     newChild = toBeRemoved.left;
  94.                 }
  95.  
  96.                 if (parent == null) // Found in root
  97.                 {
  98.                     root = newChild;
  99.                 } else if (parent.left == toBeRemoved) {
  100.                     parent.left = newChild;
  101.                 } else {
  102.                     parent.right = newChild;
  103.                 }
  104.  
  105.             } else {
  106.  
  107.                 // Neither subtree is empty
  108.  
  109.                 // Find smallest element of the right subtree
  110.  
  111.                 Node smallestParent = toBeRemoved;
  112.                 Node smallest = toBeRemoved.right;
  113.                 while (smallest.left != null) {
  114.                     smallestParent = smallest;
  115.                     smallest = smallest.left;
  116.                 }
  117.  
  118.                 // smallest contains smallest child in right subtree
  119.  
  120.                 // Move contents, unlink child
  121.  
  122.                 toBeRemoved.data = smallest.data;
  123.                 if (smallestParent == toBeRemoved) {
  124.                     smallestParent.right = smallest.right;
  125.                 } else {
  126.                     smallestParent.left = smallest.right;
  127.                 }
  128.             }
  129.         }
  130.     }
  131.  
  132.     /**
  133.      * Prints the contents of the tree in sorted order.
  134.      */
  135.     public void print() {
  136.         print(root);
  137.         System.out.println();
  138.     }
  139.  
  140.     /**
  141.      * Prints a node and all of its descendants in sorted order.
  142.      *
  143.      * @param parent the root of the subtree to print
  144.      */
  145.     private void print(Node parent) {
  146.         if (parent != null) {
  147.             print(parent.left);
  148.             System.out.print(parent.data + " ");
  149.             print(parent.right);
  150.         }
  151.     }
  152.  
  153.     /**
  154.      * A node of a tree stores a data item and references to the left and right
  155.      * child nodes.
  156.      */
  157.     private class Node {
  158.         public E data;
  159.         public Node left;
  160.         public Node right;
  161.  
  162.         public Node() {
  163.         }
  164.  
  165.         /**
  166.          * Inserts a new node as a descendant of this node.
  167.          *
  168.          * @param newNode the node to insert
  169.          */
  170.         public void addNode(Node newNode) {
  171.             int comp = newNode.data.compareTo(data);
  172.             if (comp < 0) {
  173.                 if (left == null) {
  174.                     left = newNode;
  175.                 } else {
  176.                     left.addNode(newNode);
  177.                 }
  178.             } else if (comp > 0) {
  179.                 if (right == null) {
  180.                     right = newNode;
  181.                 } else {
  182.                     right.addNode(newNode);
  183.                 }
  184.             }
  185.         }
  186.     }
  187. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top