BalancedBinarySearchTree

Iniciado por Adalher, Mayo 23, 2019, 02:24:31 PM

Tema anterior - Siguiente tema

0 Miembros y 1 Visitante están viendo este tema.

Hola a todos,

publico un árbol binario que siempre está equilibrado, i. para cada nodo, la altura del subárbol derecho difiere en un máximo de 1 desde la altura del subárbol izquierdo y un BTreeMap que lo toca.
Pero ambas clases fueron creadas solo por diversión en la alegría. En el uso real, no desempeñan ningún papel, ya que se recurre a las clases del Framework (hasta ahora no vio ninguna razón para una dependencia adicional en los proyectos).
Aquí hay una contención importante: T debe implementar Comparable <T>. De lo contrario, el valor no se puede insertar!
Código: java

package de.kneitzel.lib.collections;

/**
* A binary search tree that is always balanced.
* @param <T> Type of the values to store inside the tree.
*/
public class BalancedBinarySearchTree<T extends Comparable<T>> {

    /**
     * Gets the size of the BalancedBinarySearchTree
     * @return Numbe of elements inside the BalancedBinarySearchTree
     */
    public int size() {
        return rootNode != null ? rootNode.count : 0;
    }

    /**
     * Root node of the BalancedBinarySearchTree.
     */
    private BalancedBinarySearchTreeNode<T> rootNode;

    /**
     * Add an element to the BalancedBinarySearchTree
     * @param item
     * @return The item.
     */
    public T put(T item) {
        if (rootNode == null) {
            rootNode = new BalancedBinarySearchTreeNode<>(item);
        } else {
            rootNode.put(item);
        }
        return item;
    }

    /**
     * Remove an item of the BalancedBinarySearchTree
     * @param item Item to remove.
     * @return The item removed or null if not found.
     */
    public T remove(T item)
    {
        if (rootNode == null)
            return null;

        // Get the element first
        T element = rootNode.remove(item);
        if (rootNode.item == null) {
            rootNode = null;
        }

        // return the element.
        return element;
    }

    /**
     * Checks the BalancedBinarySearchTree. This is just an internal method which is used to unit-test the implementation.
     * @return Should always return true.
     */
    public boolean check()
    {
        return rootNode == null ? true : rootNode.check();
    }

    /**
     * Searches if an item is inside the BalancedBinarySearchTree.
     * @param item Item to search for.
     * @return the Item if found else null.
     */
    public T find(T item)
    {
        return rootNode == null ? null : rootNode.find(item);
    }

    /**
     * Tree node of the BalancedBinarySearchTree
     * @param <T> Type of the values to store inside the node.
     */
    protected class BalancedBinarySearchTreeNode<T extends Comparable<T>> {

        /**
         * Item stored inside the BalancedBinarySearchTreeNode.
         */
        public T item;

        /**
         * Child Nodes.
         */
        public BalancedBinarySearchTreeNode<T> left, right; // left and right child

        /**
         * Number of items stored inside the node and all subnodes.
         */
        public int count;

        /**
         * Height of this subtree.
         */
        public int height;

        /**
         * Creates a new instance of type BalancedBinarySearchTreeNode.
         * @param item Item to store inside this node.
         */
        public BalancedBinarySearchTreeNode(T item) {
            left = null;
            right = null;
            this.item = item;
            count = 1;
            height = 1;
        }

        /**
         * Add the item to this subtree.
         * @param item item to put.
         */
        public void put(T item) {
            // Compare the item to put with the stored item.
            int comparison = item.compareTo(this.item);

            // Override the stored item if the comparison is 0
            if (comparison == 0) {
                this.item = item;
                // Only the stored element was overridden so there is no change to count and height and
                // no need to balance the tree.
                return;
            }

            if (comparison < 0) {
                // Store the item on the left side.
                if (left == null)
                    left = new BalancedBinarySearchTreeNode<>(item);
                else
                    left.put(item);
            } else {
                // Store the item on the right side.
                if (right == null)
                    right = new BalancedBinarySearchTreeNode<>(item);
                else
                    right.put(item);
            }

            // Increase count by one
            count++;

            // Balance the tree.
            balance();
        }

        /**
         * Check the balance of the tree and rebalance it if required.
         */
        private void balance()
        {
            if ((left == null) && (right == null))
            {
                height = 1;
                return;
            }

            int leftHeight = (left != null) ? left.height : 0;
            int rightHeight = (right != null) ? right.height : 0;

            if (leftHeight + 2 <= rightHeight)
                turnLeft();

            if (rightHeight + 2 <= leftHeight)
                turnRight();

            reCalculate();
        }

        /**
         * Switch the Elements to the left
        **/
        private void turnLeft()
        {
            // First switch the items of this element with the right item
            T temp = item;
            item = right.item;
            right.item = temp;

            // Now set the references correctly
            BalancedBinarySearchTreeNode<T> tempNode = right;
            right = tempNode.right;
            tempNode.right = tempNode.left;
            tempNode.left = left;
            left = tempNode;

            left.reCalculate();
            if (right != null) right.reCalculate();
        }

        /**
         * Switch the elements to the right
        **/
        private void turnRight()
        {
            // First switch the items of this element with the right item
            T temp = item;
            item = left.item;
            left.item = temp;

            // Now set the references correctly
            BalancedBinarySearchTreeNode<T> tempNode = left;
            left = tempNode.left;
            tempNode.left = tempNode.right;
            tempNode.right = right;
            right = tempNode;

            if (left != null)
                left.reCalculate();
            right.reCalculate();
        }

        /**
         * Calculate Height and Count of this node
        **/
        private void reCalculate()
        {
            // Set Count
            count = 1 + (left == null ? 0 : left.count) + (right == null ? 0 : right.count);

            // Set Height
            int leftHeight = (left != null) ? left.height : 0;
            int rightHeight = (right != null) ? right.height : 0;
            height = ((leftHeight > rightHeight) ? leftHeight : rightHeight) + 1;
        }

        /**
         * Remove the specified item.
         * @param item Item to remove.
         * @return the removed item.
         */
        public T remove(T item)
        {
            // Compare with stored item
            int compare = item.compareTo(this.item);

            T value = null;

            if (compare < 0)
            {
                // We have to search it on the left side.
                if (left == null)
                    return null; // Not found.
                else
                {
                    value = left.remove(item);

                    if (left.item == null)
                        left = null;
                }
            } else if (compare > 0)
            {
                // We have to search it on the right side.
                if (right == null)
                    return null; // Not found
                else
                {
                    value = right.remove(item);
                    if (right.item == null)
                        right = null;
                }
            } else
            {
                // Get an item from below if possible.
                value = this.item;
                this.item = null;
                dive();
            }

            reCalculate();
            return value;
        }

        /**
         * The node with the null value is diving to the bottom of the tree and is removed afterwards.
         */
        private void dive() {
            if (right == null && left == null) {
                return;
            } else if (right == null) {
                diveLeft();
            } else if (left == null) {
                diveRight();
            } else {
                if (right.height > left.height) {
                    diveLeft();
                } else {
                    diveRight();
                }
            }
            balance();
        }

        /**
         * Continue diving on the left child.
         */
        private void diveLeft() {
            item = left.item;
            left.item = null;
            left.dive();
            if (left.item == null)
                left = null;
        }

        /**
         * Continue diving on the right child.
         */
        private void diveRight() {
            item = right.item;
            right.item = null;
            right.dive();
            if (right.item == null)
                right = null;
        }

        public T find(T key)
        {
            // Compare with stored item
            int compare = key.compareTo(item);

            // Items are equal -> Throw exception
            if (compare == 0)
                return item;

            if (compare < 0)
            {
                // We have to search it in the left subtree.
                return left == null ? null : left.find(key);
            }

            // We have to search it in the right subtree.
            return right == null ? null : right.find(key);
        }

        /**
         * Check the subtree. Should always return true.
         * @return Should always return true. If it returns false, something went wrong.
         */
        public boolean check()
        {
            // Store the height of child-trees
            int leftHeight = 0;
            int rightHeight = 0;

            // Check the left child
            if (left != null)
            {
                // Recursive check!
                if (!left.check()) return false;

                // Check sorting of values
                if (item.compareTo(left.item) <= 0)
                    return false;

                leftHeight = left.height;
            }

            // Check the right child
            if (right != null)
            {
                // Recursive check!
                if (!right.check()) return false;

                // Check sorting of values
                if (item.compareTo(right.item) >= 0)
                    return false;

                rightHeight = right.height;
            }

            // Compare Heights
            if ((rightHeight - leftHeight > 1) || (leftHeight - rightHeight > 1))
                return false;

            // Last Check: Control Count
            return count == 1 + (left == null ? 0 : left.count) + (right == null ? 0 : right.count);
        }
    }
}


Por supuesto, esto también se puede utilizar para un Map. Entonces, en primer lugar, para el mapa vale aquí en este punto, que otra vez Key también tiene que implementar Comparable<Key> como restricción.
Código: java

package de.kneitzel.lib.collections;

/**
* Dictionary which uses the Balanced Binary Search Tree.
*/
public class BTreeMap<K extends Comparable<K>, V>  {

    /**
     * A set of key and value to store the dictionary data inside the BTree.
     * @param <K> Key type.
     * @param <V> Value type.
     */
    protected class DataSet<K extends Comparable<K>, V> implements Comparable<DataSet<K,V>>{
        public K key;
        public V value;

        public DataSet(K key) {
            this.key = key;
        }

        public DataSet(K key, V value) {
            this.key = key;
            this.value = value;
        }

        /**
         * Compare the keys of the DataSets
         * @param data The data to compare with.
         * @return The result of the key comparisons.
         */
        public int compareTo(DataSet<K,V> data) {
            return key.compareTo(data.key);
        }
    }

    private BalancedBinarySearchTree<DataSet<K,V>> values = new BalancedBinarySearchTree<>();

    /**
     * Get the value of a key.
     * @param key Key for which the value is looked up.
     * @return The value or null.
     */
    public V get(K key) {
        DataSet<K,V> valueSet =  values.find(new DataSet<K,V>(key));
        return valueSet != null ? valueSet.value : null;
    }

    /**
     * Checks if the Dictionary is empty.
     * @return true if the dictionary is empty, else true.
     */
    public boolean isEmpty() {
        return values.size() == 0;
    }

    /**
     * Put a new (key, value) pair into the dictionary. If the key already exists, the value will be changed.
     * @param key Key to use.
     * @param value Value to store.
     * @return
     */
    public V put(K key, V value) {
        values.put(new DataSet<K,V>(key, value));
        return value;
    }

    /**
     * Removes the (key, value) pair of the given key.
     * @param key Key of the (key, value) pair that should be removed.
     * @return The value of the key removed or null if not found.
     */
    public V remove(K key) {
        DataSet<K,V> value = values.remove(new DataSet(key, null));
        return value!=null ? value.value : null;
    }

    /**
     * Gets the number of elements stored inside the dictionary.
     * @return Number of elements stored inside the dictionary.
     */
    public int size() {
        return values.size();
    }
}


Quizás queramos deshacernos ahora de esa estúpida restricción en K extends Comparable<K>. Lo que se tiene que hacer ahora es solo:
a) Creamos un DataListNode <K> que recoge un elemento de K y que contiene una referencia a un DataListNode <K>.
b) Creamos un DataNode <K> que implementa Comparable <DataNode <K >> y
- que contiene el código hash
- Compare va por el código hash
- que contiene DataListNode<K>.
A continuación, su puede guardarlo en el árbol. Pero entonces las operaciones corren algo diferente:
Si se busca un elemento, se busca primero un algoritmo conocido. Pero al final se tiene un DataListNode <K> y luego se tiene que seguir buscando en el (puede dar varios elementos con un código hash). Entonces es similar para todas las demás operaciones.
Pero debo admitir que estas todavía tienen que ser implementadas.
Y al final las pruebas unitarias actuales:
Código: java

package de.kneitzel.lib.tests;

import static org.junit.Assert.*;

import de.kneitzel.lib.collections.BalancedBinarySearchTree;
import de.kneitzel.lib.collections.BTreeMap;

import org.junit.Test;
/**
* Tests for de.kneitzel.lib.collections
*/
public class CollectionsTests {

    @Test
    public void BalancedBinarySearchTreeTest()
    {
        BalancedBinarySearchTree<String> tree = new BalancedBinarySearchTree<>();
        assertTrue(tree.check());
        assertEquals(tree.size(), 0);
        assertEquals(tree.put("aaa"), "aaa");
        assertTrue(tree.check());
        assertEquals(tree.size(), 1);
        assertEquals(tree.put("bbb"), "bbb");
        assertTrue(tree.check());
        assertEquals(tree.size(), 2);
        assertEquals(tree.put("ccc"), "ccc");
        assertTrue(tree.check());
        assertEquals(tree.size(), 3);
        assertEquals(tree.put("ddd"), "ddd");
        assertTrue(tree.check());
        assertEquals(tree.size(), 4);
        assertEquals(tree.put("eee"), "eee");
        assertTrue(tree.check());
        assertEquals(tree.size(), 5);
        assertEquals(tree.put("xxx"), "xxx");
        assertTrue(tree.check());
        assertEquals(tree.size(), 6);
        assertEquals(tree.put("yyy"), "yyy");
        assertTrue(tree.check());
        assertEquals(tree.size(), 7);
        assertEquals(tree.put("zzz"), "zzz");
        assertTrue(tree.check());
        assertEquals(tree.size(), 8);
        assertEquals(tree.put("iii"), "iii");
        assertTrue(tree.check());
        assertEquals(tree.size(), 9);
        assertEquals(tree.put("jjj"), "jjj");
        assertTrue(tree.check());
        assertEquals(tree.size(), 10);
        assertEquals(tree.find("aaa"), "aaa");
        assertEquals(tree.find("bbb"), "bbb");
        assertEquals(tree.find("ccc"), "ccc");
        assertEquals(tree.find("ddd"), "ddd");
        assertNull(tree.find("fff"));
        try {
            assertEquals(tree.remove("ccc"), "ccc");
            assertEquals(tree.size(), 9);
        } catch (Exception e)
        {
            fail("Shouldn't throw an exception!");
        }
        assertNull(tree.find("ccc"));
        assertEquals(tree.find("aaa"), "aaa");
        assertEquals(tree.find("bbb"), "bbb");
        assertEquals(tree.find("ddd"), "ddd");
    }

    @Test
    public void BTreeMapTest() {
        BTreeMap<String, String> map = new BTreeMap<>();
        assertTrue(map.isEmpty());
        assertEquals(map.size(), 0);
        assertNull(map.get("test"));
        assertEquals(map.put("aaa", "AAA"), "AAA");
        assertEquals(map.size(), 1);
        assertFalse(map.isEmpty());
        assertEquals(map.get("aaa"), "AAA");
        assertFalse(map.isEmpty());
        assertEquals(map.remove("aaa"), "AAA");
        assertEquals(map.size(), 0);
        assertTrue(map.isEmpty());
        assertEquals(map.put("aaa", "AAA"), "AAA");
        assertEquals(map.size(), 1);
        assertFalse(map.isEmpty());
        assertEquals(map.put("bbb", "BBB"), "BBB");
        assertEquals(map.size(), 2);
        assertFalse(map.isEmpty());
        assertEquals(map.put("ccc", "CCC"), "CCC");
        assertEquals(map.size(), 3);
        assertFalse(map.isEmpty());
        assertEquals(map.put("ddd", "DDD"), "DDD");
        assertEquals(map.size(), 4);
        assertFalse(map.isEmpty());
        assertEquals(map.put("eee", "EEE"), "EEE");
        assertEquals(map.size(), 5);
        assertFalse(map.isEmpty());
        assertNull(map.get("fff"));
        assertNull(map.remove("fff"));
        assertEquals(map.get("aaa"), "AAA");
        assertFalse(map.isEmpty());
        assertEquals(map.get("bbb"), "BBB");
        assertFalse(map.isEmpty());
        assertEquals(map.get("ccc"), "CCC");
        assertFalse(map.isEmpty());
        assertEquals(map.get("ddd"), "DDD");
        assertFalse(map.isEmpty());
        assertEquals(map.get("eee"), "EEE");
        assertFalse(map.isEmpty());
        assertEquals("BBB", map.remove("bbb"));
        assertFalse(map.isEmpty());
        assertEquals("CCC", map.remove("ccc"));
        assertFalse(map.isEmpty());
        assertEquals(map.remove("ddd"), "DDD");
        assertFalse(map.isEmpty());
        assertEquals(map.remove("aaa"), "AAA");
        assertFalse(map.isEmpty());
        assertEquals(map.remove("eee"), "EEE");
        assertTrue(map.isEmpty());
        assertNull(map.get("fff"));
        assertNull(map.remove("fff"));
    }
}


Saludos
Este es el mayor reproche al pueblo hispanohablante:

Que a pesar de su inteligencia y a pesar de su valentía siempre adoran el poder.