27. Linked Binary Search Trees

  • Given the way the binary search tree ideas were presented, a linked implementation may feel like an obvious choice

    • Though, there is nothing preventing an array based implementation

27.1. Constructors

 6public class LinkedBinarySearchTree<T extends Comparable<? super T>> implements BinarySearchTree<T> {
 7
 8    private int size;
 9    private Node<T> root;
10
11    public LinkedBinarySearchTree() {
12        root = null;
13        size = 0;
14    }

  • Like the other implementations, this class implements the interface

  • The data structure is to be generic

  • Like the sorted bag, since it is concerned with the ordering, ensure that the objects are comparable

  • There is a single constructor to create an empty binary search tree

27.2. Static Node Class

  • Notice the use of Node<T> root

  • Like the linked stack and linked queue, this linked binary search tree will make use of nodes

  • To keep things clean, a nested node class is used

462    /**
463     * A node class for a linked binary tree structure. Each node contains a nullable reference to data of type T, and a
464     * reference to the left and right child nodes, which may be null references.
465     *
466     * @param <T> Type of the data being stored in the node
467     */
468    private static class Node<T> {
469        private T data;
470        private Node<T> left;
471        private Node<T> right;
472
473        private Node() {
474            this(null);
475        }
476
477        private Node(T data) {
478            this.data = data;
479            this.left = null;
480            this.right = null;
481        }
482
483        private T getData() {
484            return data;
485        }
486
487        private void setData(T data) {
488            this.data = data;
489        }
490
491        private Node<T> getLeft() {
492            return left;
493        }
494
495        private void setLeft(Node<T> left) {
496            this.left = left;
497        }
498
499        private Node<T> getRight() {
500            return right;
501        }
502
503        private void setRight(Node<T> right) {
504            this.right = right;
505        }
506    }

  • Things of note for this node class

    • This is a binary tree node, thus it has a left and right reference for the left and right subtrees

    • This nested static class is contained within the LinkedBinarySearchTree class

27.3. Add to Binary Search Tree

18    @Override
19    public boolean add(T element) {
20        root = add(element, root);
21        size++;
22        return true;
23    }
24
25    /**
26     * Helper add method for enabling recursive add. This method ensures that elements are added in the proper order for
27     * a Binary Search Tree.
28     *
29     * @param element Element to be added to the tree
30     * @param current Current root of subtree
31     * @return Node being assigned as left/right child
32     */
33    private Node<T> add(T element, Node<T> current) {
34        if (current == null) {
35            return new Node<>(element);
36        }
37        if (current.getData().compareTo(element) > 0) {
38            current.setLeft(add(element, current.getLeft()));
39        } else {
40            current.setRight(add(element, current.getRight()));
41        }
42        return current;
43    }

  • A public method is used to call the private recursive add with initial values

  • This method is very similar to a binary search

  • Keep going left/right down the tree based on the ordering of the tree and value of the element being added

  • As soon as an empty spot is found, insert the node there

  • The inserted value will be in a leaf node

27.4. Minimum & Maximum

204    @Override
205    public T min() {
206        if (isEmpty()) {
207            throw new NoSuchElementException("Empty Tree");
208        }
209        return min(root);
210    }
211
212    /**
213     * Helper method for enabling a recursive search for the minimum element in the binary search tree.
214     *
215     * @param current Current node being looked at
216     * @return The minimum element in the tree
217     */
218    private T min(Node<T> current) {
219        if (current.getLeft() == null) {
220            return current.getData();
221        } else {
222            return min(current.getLeft());
223        }
224    }
225
226    @Override
227    public T max() {
228        if (isEmpty()) {
229            throw new NoSuchElementException("Empty Tree");
230        }
231        Node<T> current = root;
232        // Iterate right until right most node is found
233        while (current.getRight() != null) {
234            current = current.getRight();
235        }
236        return current.getData();
237    }

  • Fortunately the minimum and maximum methods are simple

  • Due to the ordered nature of the binary search tree, go all the way to the left/right for the minimum/maximum value

  • The minimum functionality is implemented recursively and the maximum is implemented iteratively

    • This is done for demonstration purposes only

27.5. Remove Minimum & Maximum

  • Finding the minimum and maximum values in the linked binary search tree is relatively simple

  • However, removing from the tree adds extra complexity as there is a need to preserve the binary search tree ordering of the tree

27.5.1. Remove Minimum

138    @Override
139    public T removeMin() {
140        T returnElement = null;
141        if (isEmpty()) {
142            throw new NoSuchElementException("Empty Tree");
143        } else if (root.getLeft() == null) {
144            returnElement = root.getData();
145            root = root.getRight();
146        } else {
147            returnElement = removeMin(root, root.getLeft());
148        }
149        size--;
150        return returnElement;
151    }
152
153    /**
154     * Helper method for a recursive removeMin.
155     *
156     * @param parent  The parent of the current node
157     * @param current The current node
158     * @return Minimum element in the binary search tree
159     */
160    private T removeMin(Node<T> parent, Node<T> current) {
161        if (current.getLeft() == null) {
162            parent.setLeft(current.getRight());
163            return current.getData();
164        } else {
165            return removeMin(current, current.getLeft());
166        }
167    }

  • Above are two methods that work together to remove the minimum value

  • First, take note of the public method

    • It checks if the tree is empty

    • It checks if the root happens to be the left most node

      • If it is, then make the root’s right child the new root of the whole tree

    • Otherwise, call the private recursive method looking down the left subtree

  • If the public method doesn’t remove the minimum, the recursive private method is the one that goes looking for the minimum to remove

  • At this point, current exists (is not null) since this was checked in the calling method

    • Remember, if the root’s left child does not exist, then the root must contain the minimum value in the tree

  • Start with the recursive case — if current’s left child does exist, then call the recursive function again to keep looking down the left subtrees

  • If current’s left subtree does not exist, then current contains the minimum value

    • Simply replace parent’s left child (which current also references) with current’s right child

      • It does not matter if current’s right child is null or not, it works either way

27.5.2. Remove Maximum

  • removeMax could be implemented with the same recursive idea as removeMin

  • However, for demonstration purposes, an iterative method is used instead

171    /**
172     * An iterative implementation of finding the maximum element in a binary search tree. This method could be
173     * recursive like removeMin; however, the iterative one is included for demonstrative purposes.
174     *
175     * @return The maximum element in the binary search tree
176     */
177    @Override
178    public T removeMax() {
179        T returnElement = null;
180        if (isEmpty()) {
181            throw new NoSuchElementException("Empty Tree");
182        }
183        if (root.getRight() == null) {
184            returnElement = root.getData();
185            root = root.getLeft();
186        } else {
187            Node<T> parent = root;
188            Node<T> current = root.getRight();
189            // Iterate right until right most node is found
190            while (current.getRight() != null) {
191                parent = current;
192                current = current.getRight();
193            }
194            returnElement = current.getData();
195            parent.setRight(current.getLeft());
196        }
197        size--;
198        return returnElement;
199    }

  • removeMax is similar to the public removeMin method

    • Check if the root exists

    • Check if the root’s right exists

  • It’s the else case that’s different

  • The idea is, loop down to the right until there is no more right children

  • Then, once the right most node is found, set it’s parent’s right child to the node being removed’s left child

    • Again, it doesn’t matter if the left child is null or not

27.6. General Remove

  • This is probably the most complex functionality discussed this course

  • To help, the discussion will be broken up

47    @Override
48    public boolean remove(T element) {
49        if (!contains(element)) {
50            return false;
51        }
52        int comparison = root.getData().compareTo(element);
53        if (comparison == 0) {
54            root = findReplacementNode(root);
55        } else if (comparison > 0) {
56            remove(element, root, root.getLeft());
57        } else {
58            remove(element, root, root.getRight());
59        }
60        size--;
61        return true;
62    }

  • The public remove method is similar to the public removeMin and removeMax

  • It checks the root node to see if it is the value to be removed

  • Otherwise, it checks which subtree to continue the search down and calls the recursive private remove

66    /**
67     * Helper method for recursive remove.
68     *
69     * @param element Element to me removed
70     * @param parent  The parent of the current node
71     * @param current The current node
72     * @return The element being removed
73     */
74    private T remove(T element, Node<T> parent, Node<T> current) {
75        int comparison = current.getData().compareTo(element);
76        if (comparison == 0) {
77            if (parent.getData().compareTo(current.getData()) > 0) {
78                parent.setLeft(findReplacementNode(current));
79            } else {
80                parent.setRight(findReplacementNode(current));
81            }
82            return current.getData();
83        } else if (comparison > 0) {
84            return remove(element, current, current.getLeft());
85        } else {
86            return remove(element, current, current.getRight());
87        }
88    }

  • The private remove is basically doing a binary search through the tree looking for the value to be removed

  • Unlike the binary search however, this method must

    • Remove the element

    • Potentially address a gap in the tree if the node being removed is an internal node

    • Ensure the binary search tree ordering is preserved

  • To do this, another private method called findReplacementNode is used

 93    /**
 94     * Helper method for finding which node should be used to replace a node being removed.
 95     * There are a few conditions:
 96     * 1. Both left and right children are null. Here, simply remove the node.
 97     * 2. Left child is not null but right child is null. Replace the toRemove node with the left child.
 98     * 3. Left child is null but right child is not null. Replace the toRemove node with the right child.
 99     * 4. Both left and right children are not null. Replace the toRemove node with the in order successor, which would
100     * be the right subtree's left most node.
101     *
102     * @param toRemove The node being replaced
103     * @return The node replacing the node being removed
104     */
105    private Node<T> findReplacementNode(Node<T> toRemove) {
106        Node<T> replacementNode = null;
107        if (toRemove.getLeft() == null && toRemove.getRight() == null) {
108            replacementNode = null;
109        } else if (toRemove.getLeft() != null && toRemove.getRight() == null) {
110            replacementNode = toRemove.getLeft();
111        } else if (toRemove.getLeft() == null && toRemove.getRight() != null) {
112            replacementNode = toRemove.getRight();
113        } else {
114            Node<T> parent = toRemove;
115            Node<T> current = toRemove.getRight();
116            // Find the in order successor --- toRemove's right child's left most node (minimum node)
117            while (current.getLeft() != null) {
118                parent = current;
119                current = current.getLeft();
120            }
121            replacementNode = current;
122            // Set replacementNode's left to toRemove's left
123            replacementNode.setLeft(toRemove.getLeft());
124            // Update replacementNode's right if necessary --- if the in order successor of toRemove is its immediate
125            // right, no update is needed. Otherwise, the replacementNode's parent's left is set to the
126            // replacementNode's right and the replacementNode's right is set to toRemove's right.
127            if (toRemove.getRight() != replacementNode) {
128                parent.setLeft(replacementNode.getRight());
129                replacementNode.setRight(toRemove.getRight());
130            }
131        }
132        return replacementNode;
133    }

  • findReplacementNode looks rather intimidating at first, but if studied carefully, it is actually rather simple

  • The first part, the first if s and else if s check if the node being removed is a leaf node, or if it has one child

    • If it’s a leaf node, there is no replacement

    • If there is only one child, then that child becomes the replacement

  • The other case is when there are two children

  • Here, the idea is to find the in order successor node

    • The right child’s left most node

  • This code is very similar to the private removeMax method

    • Iterate down the tree until the left most node in the subtree is found

    • This node will become the replacement node

  • The replacement node’s left subtree will be the removed node’s old left subtree

    • The replacement node contains the smallest thing in the whole right subtree

    • But since it is in the right subtree, it is bigger than everything in the removed node’s left subtree

  • If it happens that the node being removed’s right child is the replacement node, then done

  • If it is not the right child, then

    • The replacement node’s parent may need to take care of the replacement node’s right subtree

    • The node being removed may have a right subtree, that when all is said and done, still needs to go somewhere

  • The idea is, since the parent to the replacement node must be larger than everything in its left subtree, the replacement node’s right subtree is also less than the parent

    • Therefore, make the parent node’s new left subtree the replacement node’s right subtree

  • Since the replacement node is the smallest thing in the right subtree, the replacement node’s right subtree can be made to be the removed node’s right subtree

27.7. contains

  • All data structures implemented have a way to check if a given element is contained within it

  • The binary search tree is no different, but here a linear search will not be used

  • Instead, make use of a binary search to help find the element within the data structure

241    @Override
242    public boolean contains(T element) {
243        return binarySearch(element, root) != null;
244    }
245
246    /**
247     * Helper method enabling a recursive binary search for a given element.
248     *
249     * @param element Element being searched for
250     * @param current Current node being investigated
251     * @return Node containing the element searched for, or null if not found
252     */
253    private Node<T> binarySearch(T element, Node<T> current) {
254        if (current == null) {
255            return null;
256        }
257        int comparison = current.getData().compareTo(element);
258        if (comparison == 0) {
259            return current;
260        } else {
261            if (comparison > 0) {
262                return binarySearch(element, current.getLeft());
263            } else {
264                return binarySearch(element, current.getRight());
265            }
266        }
267    }

  • See the above method called contains and the recursive binarySearch method

  • What’s interesting here is contains needs to return a boolean, but the binarySearch returns a reference to a node

  • A way to address this is to simply check if binarySearch returned a reference to a node or not

    • If contains gets a node back, then return true

    • Otherwise, if null, return false

  • As this method is written, duplicate values are assumed to be in the right subtree

27.8. count

271    @Override
272    public int count(T element) {
273        if (isEmpty()) {
274            return 0;
275        }
276        return count(element, root);
277    }
278
279    /**
280     * Helper method for recursive count of elements in binary search tree.
281     *
282     * @param element Element to be counted
283     * @param current Current node being investigated
284     * @return Number of times the element exists in the (sub)tree
285     */
286    private int count(T element, Node<T> current) {
287        if (current == null) {
288            return 0;
289        }
290        int comparison = current.getData().compareTo(element);
291        if (comparison == 0) {
292            // With this implementation, equal elements are always to the right
293            return 1 + count(element, current.getRight());
294        } else if (comparison > 0) {
295            return count(element, current.getLeft());
296        } else {
297            return count(element, current.getRight());
298        }
299    }

  • Counting the number of times a given element exists within the tree will be similar to a binary search

  • The key difference will be, do a binary search, but if the element is found, continue looking in the subtree where duplicates are added

  • Notice the line return 1 + count(element, current.getRight())

    • This continues the search to the right

    • Whatever the result of the search down the right subtree returns, add one to it before returning

27.9. For Next Time

  • Read Chapter 11 Sections 1 – 3

    • 17 pages

27.9.1. Playing Code