Binary Trees and Heaps: Implementation in Java
Binary Trees
First Element
The first() method returns the first element in the binary tree by recursively traversing the left subtree until it reaches the leftmost node.
Last Element
The last() method returns the last element in the binary tree by iteratively traversing the right subtree until it reaches the rightmost node.
Add Element
The add(E item) method adds an element to the binary tree while maintaining its sorted order. It first checks if the element already exists and returns false if it does. Otherwise, it traverses the tree, comparing the new element with the current node’s data. If the new element is smaller, it moves to the left subtree; if it’s larger, it moves to the right subtree. When it reaches a null node, it inserts the new element there and updates the size of the tree.
Contains Element
The contains(Object arg0) method checks if an element exists in the binary tree. It recursively traverses the tree, comparing the target element with the current node’s data. If they are equal, it returns true. If the target element is smaller, it moves to the left subtree; if it’s larger, it moves to the right subtree. If it reaches a null node, it returns false.
Remove Element
The remove(Object arg0) method removes an element from the binary tree while maintaining its sorted order. It recursively searches for the element to remove. If it finds the element, it handles three cases: 1) If the node has two children, it replaces the node’s data with the minimum element from the right subtree and recursively removes the minimum element. 2) If the node has only a left child, it replaces the node with its left child. 3) If the node has only a right child or no children, it replaces the node with its right child or null, respectively.
Ceiling Element
The ceiling(E e) method finds the smallest element in the binary tree that is greater than or equal to the given element e. It traverses the tree, keeping track of the maximum element found so far that is less than or equal to e. If it finds an element equal to e, it returns that element. Otherwise, it returns the maximum element found during the traversal.
Heaps
Sink Operation
The sink(int parent) method is used to maintain the heap property in a min-heap. It compares the parent node with its children and swaps it with the smaller child if necessary. This process is repeated recursively until the heap property is restored.
Floating Operation
The floating(int child) method is used to maintain the heap property in a min-heap after inserting a new element. It compares the child node with its parent and swaps them if the child is smaller. This process is repeated recursively until the heap property is restored.
Heapify Operation
The heapify() method transforms an array into a min-heap by calling the sink() method on all non-leaf nodes in reverse order.
IndexOf Operation
The indexOf(E item, int current) method searches for an element in the heap and returns its index. It recursively traverses the heap, comparing the target element with the current node’s data. If they are equal, it returns the current index. If the target element is smaller, it moves to the left subtree; if it’s larger, it moves to the right subtree. If it reaches a null node or the target element is not found, it returns -1.
Add Element
The add(E item) method adds an element to the heap while maintaining the heap property. It inserts the new element at the end of the heap and then calls the floating() method to restore the heap property.
Remove Element
The remove(E item) method removes an element from the heap while maintaining the heap property. It first finds the index of the element using the indexOf() method. If the element is found, it swaps it with the last element in the heap, decreases the size of the heap, and then calls either the sink() or floating() method to restore the heap property.
Grow Operation
The grow() method doubles the capacity of the heap when it becomes full. It creates a new array with twice the capacity, copies the elements from the old array to the new array, and updates the data array reference.