Este sitio utiliza cookies propias y de terceros. Si continúa navegando consideramos que acepta el uso de cookies. OK Más Información.

BalancedBinarySearchTree

  • 0 Respuestas
  • 410 Vistas

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

Desconectado Adalher

  • *
  • Underc0der
  • Mensajes: 36
  • Actividad:
    6.67%
  • Reputación 0
    • Ver Perfil
« en: Mayo 23, 2019, 02:24:31 pm »
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
  1. package de.kneitzel.lib.collections;
  2.  
  3. /**
  4. * A binary search tree that is always balanced.
  5. * @param <T> Type of the values to store inside the tree.
  6. */
  7. public class BalancedBinarySearchTree<T extends Comparable<T>> {
  8.  
  9.     /**
  10.      * Gets the size of the BalancedBinarySearchTree
  11.      * @return Numbe of elements inside the BalancedBinarySearchTree
  12.      */
  13.     public int size() {
  14.         return rootNode != null ? rootNode.count : 0;
  15.     }
  16.  
  17.     /**
  18.      * Root node of the BalancedBinarySearchTree.
  19.      */
  20.     private BalancedBinarySearchTreeNode<T> rootNode;
  21.  
  22.     /**
  23.      * Add an element to the BalancedBinarySearchTree
  24.      * @param item
  25.      * @return The item.
  26.      */
  27.     public T put(T item) {
  28.         if (rootNode == null) {
  29.             rootNode = new BalancedBinarySearchTreeNode<>(item);
  30.         } else {
  31.             rootNode.put(item);
  32.         }
  33.         return item;
  34.     }
  35.  
  36.     /**
  37.      * Remove an item of the BalancedBinarySearchTree
  38.      * @param item Item to remove.
  39.      * @return The item removed or null if not found.
  40.      */
  41.     public T remove(T item)
  42.     {
  43.         if (rootNode == null)
  44.             return null;
  45.  
  46.         // Get the element first
  47.         T element = rootNode.remove(item);
  48.         if (rootNode.item == null) {
  49.             rootNode = null;
  50.         }
  51.  
  52.         // return the element.
  53.         return element;
  54.     }
  55.  
  56.     /**
  57.      * Checks the BalancedBinarySearchTree. This is just an internal method which is used to unit-test the implementation.
  58.      * @return Should always return true.
  59.      */
  60.     public boolean check()
  61.     {
  62.         return rootNode == null ? true : rootNode.check();
  63.     }
  64.  
  65.     /**
  66.      * Searches if an item is inside the BalancedBinarySearchTree.
  67.      * @param item Item to search for.
  68.      * @return the Item if found else null.
  69.      */
  70.     public T find(T item)
  71.     {
  72.         return rootNode == null ? null : rootNode.find(item);
  73.     }
  74.  
  75.     /**
  76.      * Tree node of the BalancedBinarySearchTree
  77.      * @param <T> Type of the values to store inside the node.
  78.      */
  79.     protected class BalancedBinarySearchTreeNode<T extends Comparable<T>> {
  80.  
  81.         /**
  82.          * Item stored inside the BalancedBinarySearchTreeNode.
  83.          */
  84.         public T item;
  85.  
  86.         /**
  87.          * Child Nodes.
  88.          */
  89.         public BalancedBinarySearchTreeNode<T> left, right; // left and right child
  90.  
  91.         /**
  92.          * Number of items stored inside the node and all subnodes.
  93.          */
  94.         public int count;
  95.  
  96.         /**
  97.          * Height of this subtree.
  98.          */
  99.         public int height;
  100.  
  101.         /**
  102.          * Creates a new instance of type BalancedBinarySearchTreeNode.
  103.          * @param item Item to store inside this node.
  104.          */
  105.         public BalancedBinarySearchTreeNode(T item) {
  106.             left = null;
  107.             right = null;
  108.             this.item = item;
  109.             count = 1;
  110.             height = 1;
  111.         }
  112.  
  113.         /**
  114.          * Add the item to this subtree.
  115.          * @param item item to put.
  116.          */
  117.         public void put(T item) {
  118.             // Compare the item to put with the stored item.
  119.             int comparison = item.compareTo(this.item);
  120.  
  121.             // Override the stored item if the comparison is 0
  122.             if (comparison == 0) {
  123.                 this.item = item;
  124.                 // Only the stored element was overridden so there is no change to count and height and
  125.                 // no need to balance the tree.
  126.                 return;
  127.             }
  128.  
  129.             if (comparison < 0) {
  130.                 // Store the item on the left side.
  131.                 if (left == null)
  132.                     left = new BalancedBinarySearchTreeNode<>(item);
  133.                 else
  134.                     left.put(item);
  135.             } else {
  136.                 // Store the item on the right side.
  137.                 if (right == null)
  138.                     right = new BalancedBinarySearchTreeNode<>(item);
  139.                 else
  140.                     right.put(item);
  141.             }
  142.  
  143.             // Increase count by one
  144.             count++;
  145.  
  146.             // Balance the tree.
  147.             balance();
  148.         }
  149.  
  150.         /**
  151.          * Check the balance of the tree and rebalance it if required.
  152.          */
  153.         private void balance()
  154.         {
  155.             if ((left == null) && (right == null))
  156.             {
  157.                 height = 1;
  158.                 return;
  159.             }
  160.  
  161.             int leftHeight = (left != null) ? left.height : 0;
  162.             int rightHeight = (right != null) ? right.height : 0;
  163.  
  164.             if (leftHeight + 2 <= rightHeight)
  165.                 turnLeft();
  166.  
  167.             if (rightHeight + 2 <= leftHeight)
  168.                 turnRight();
  169.  
  170.             reCalculate();
  171.         }
  172.  
  173.         /**
  174.          * Switch the Elements to the left
  175.         **/
  176.         private void turnLeft()
  177.         {
  178.             // First switch the items of this element with the right item
  179.             T temp = item;
  180.             item = right.item;
  181.             right.item = temp;
  182.  
  183.             // Now set the references correctly
  184.             BalancedBinarySearchTreeNode<T> tempNode = right;
  185.             right = tempNode.right;
  186.             tempNode.right = tempNode.left;
  187.             tempNode.left = left;
  188.             left = tempNode;
  189.  
  190.             left.reCalculate();
  191.             if (right != null) right.reCalculate();
  192.         }
  193.  
  194.         /**
  195.          * Switch the elements to the right
  196.         **/
  197.         private void turnRight()
  198.         {
  199.             // First switch the items of this element with the right item
  200.             T temp = item;
  201.             item = left.item;
  202.             left.item = temp;
  203.  
  204.             // Now set the references correctly
  205.             BalancedBinarySearchTreeNode<T> tempNode = left;
  206.             left = tempNode.left;
  207.             tempNode.left = tempNode.right;
  208.             tempNode.right = right;
  209.             right = tempNode;
  210.  
  211.             if (left != null)
  212.                 left.reCalculate();
  213.             right.reCalculate();
  214.         }
  215.  
  216.         /**
  217.          * Calculate Height and Count of this node
  218.         **/
  219.         private void reCalculate()
  220.         {
  221.             // Set Count
  222.             count = 1 + (left == null ? 0 : left.count) + (right == null ? 0 : right.count);
  223.  
  224.             // Set Height
  225.             int leftHeight = (left != null) ? left.height : 0;
  226.             int rightHeight = (right != null) ? right.height : 0;
  227.             height = ((leftHeight > rightHeight) ? leftHeight : rightHeight) + 1;
  228.         }
  229.  
  230.         /**
  231.          * Remove the specified item.
  232.          * @param item Item to remove.
  233.          * @return the removed item.
  234.          */
  235.         public T remove(T item)
  236.         {
  237.             // Compare with stored item
  238.             int compare = item.compareTo(this.item);
  239.  
  240.             T value = null;
  241.  
  242.             if (compare < 0)
  243.             {
  244.                 // We have to search it on the left side.
  245.                 if (left == null)
  246.                     return null; // Not found.
  247.                 else
  248.                 {
  249.                     value = left.remove(item);
  250.  
  251.                     if (left.item == null)
  252.                         left = null;
  253.                 }
  254.             } else if (compare > 0)
  255.             {
  256.                 // We have to search it on the right side.
  257.                 if (right == null)
  258.                     return null; // Not found
  259.                 else
  260.                 {
  261.                     value = right.remove(item);
  262.                     if (right.item == null)
  263.                         right = null;
  264.                 }
  265.             } else
  266.             {
  267.                 // Get an item from below if possible.
  268.                 value = this.item;
  269.                 this.item = null;
  270.                 dive();
  271.             }
  272.  
  273.             reCalculate();
  274.             return value;
  275.         }
  276.  
  277.         /**
  278.          * The node with the null value is diving to the bottom of the tree and is removed afterwards.
  279.          */
  280.         private void dive() {
  281.             if (right == null && left == null) {
  282.                 return;
  283.             } else if (right == null) {
  284.                 diveLeft();
  285.             } else if (left == null) {
  286.                 diveRight();
  287.             } else {
  288.                 if (right.height > left.height) {
  289.                     diveLeft();
  290.                 } else {
  291.                     diveRight();
  292.                 }
  293.             }
  294.             balance();
  295.         }
  296.  
  297.         /**
  298.          * Continue diving on the left child.
  299.          */
  300.         private void diveLeft() {
  301.             item = left.item;
  302.             left.item = null;
  303.             left.dive();
  304.             if (left.item == null)
  305.                 left = null;
  306.         }
  307.  
  308.         /**
  309.          * Continue diving on the right child.
  310.          */
  311.         private void diveRight() {
  312.             item = right.item;
  313.             right.item = null;
  314.             right.dive();
  315.             if (right.item == null)
  316.                 right = null;
  317.         }
  318.  
  319.         public T find(T key)
  320.         {
  321.             // Compare with stored item
  322.             int compare = key.compareTo(item);
  323.  
  324.             // Items are equal -> Throw exception
  325.             if (compare == 0)
  326.                 return item;
  327.  
  328.             if (compare < 0)
  329.             {
  330.                 // We have to search it in the left subtree.
  331.                 return left == null ? null : left.find(key);
  332.             }
  333.  
  334.             // We have to search it in the right subtree.
  335.             return right == null ? null : right.find(key);
  336.         }
  337.  
  338.         /**
  339.          * Check the subtree. Should always return true.
  340.          * @return Should always return true. If it returns false, something went wrong.
  341.          */
  342.         public boolean check()
  343.         {
  344.             // Store the height of child-trees
  345.             int leftHeight = 0;
  346.             int rightHeight = 0;
  347.  
  348.             // Check the left child
  349.             if (left != null)
  350.             {
  351.                 // Recursive check!
  352.                 if (!left.check()) return false;
  353.  
  354.                 // Check sorting of values
  355.                 if (item.compareTo(left.item) <= 0)
  356.                     return false;
  357.  
  358.                 leftHeight = left.height;
  359.             }
  360.  
  361.             // Check the right child
  362.             if (right != null)
  363.             {
  364.                 // Recursive check!
  365.                 if (!right.check()) return false;
  366.  
  367.                 // Check sorting of values
  368.                 if (item.compareTo(right.item) >= 0)
  369.                     return false;
  370.  
  371.                 rightHeight = right.height;
  372.             }
  373.  
  374.             // Compare Heights
  375.             if ((rightHeight - leftHeight > 1) || (leftHeight - rightHeight > 1))
  376.                 return false;
  377.  
  378.             // Last Check: Control Count
  379.             return count == 1 + (left == null ? 0 : left.count) + (right == null ? 0 : right.count);
  380.         }
  381.     }
  382. }
  383.  

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
  1. package de.kneitzel.lib.collections;
  2.  
  3. /**
  4. * Dictionary which uses the Balanced Binary Search Tree.
  5. */
  6. public class BTreeMap<K extends Comparable<K>, V>  {
  7.  
  8.     /**
  9.      * A set of key and value to store the dictionary data inside the BTree.
  10.      * @param <K> Key type.
  11.      * @param <V> Value type.
  12.      */
  13.     protected class DataSet<K extends Comparable<K>, V> implements Comparable<DataSet<K,V>>{
  14.         public K key;
  15.         public V value;
  16.  
  17.         public DataSet(K key) {
  18.             this.key = key;
  19.         }
  20.  
  21.         public DataSet(K key, V value) {
  22.             this.key = key;
  23.             this.value = value;
  24.         }
  25.  
  26.         /**
  27.          * Compare the keys of the DataSets
  28.          * @param data The data to compare with.
  29.          * @return The result of the key comparisons.
  30.          */
  31.         public int compareTo(DataSet<K,V> data) {
  32.             return key.compareTo(data.key);
  33.         }
  34.     }
  35.  
  36.     private BalancedBinarySearchTree<DataSet<K,V>> values = new BalancedBinarySearchTree<>();
  37.  
  38.     /**
  39.      * Get the value of a key.
  40.      * @param key Key for which the value is looked up.
  41.      * @return The value or null.
  42.      */
  43.     public V get(K key) {
  44.         DataSet<K,V> valueSet =  values.find(new DataSet<K,V>(key));
  45.         return valueSet != null ? valueSet.value : null;
  46.     }
  47.  
  48.     /**
  49.      * Checks if the Dictionary is empty.
  50.      * @return true if the dictionary is empty, else true.
  51.      */
  52.     public boolean isEmpty() {
  53.         return values.size() == 0;
  54.     }
  55.  
  56.     /**
  57.      * Put a new (key, value) pair into the dictionary. If the key already exists, the value will be changed.
  58.      * @param key Key to use.
  59.      * @param value Value to store.
  60.      * @return
  61.      */
  62.     public V put(K key, V value) {
  63.         values.put(new DataSet<K,V>(key, value));
  64.         return value;
  65.     }
  66.  
  67.     /**
  68.      * Removes the (key, value) pair of the given key.
  69.      * @param key Key of the (key, value) pair that should be removed.
  70.      * @return The value of the key removed or null if not found.
  71.      */
  72.     public V remove(K key) {
  73.         DataSet<K,V> value = values.remove(new DataSet(key, null));
  74.         return value!=null ? value.value : null;
  75.     }
  76.  
  77.     /**
  78.      * Gets the number of elements stored inside the dictionary.
  79.      * @return Number of elements stored inside the dictionary.
  80.      */
  81.     public int size() {
  82.         return values.size();
  83.     }
  84. }
  85.  

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
  1. package de.kneitzel.lib.tests;
  2.  
  3. import static org.junit.Assert.*;
  4.  
  5. import de.kneitzel.lib.collections.BalancedBinarySearchTree;
  6. import de.kneitzel.lib.collections.BTreeMap;
  7.  
  8. import org.junit.Test;
  9. /**
  10. * Tests for de.kneitzel.lib.collections
  11. */
  12. public class CollectionsTests {
  13.  
  14.     @Test
  15.     public void BalancedBinarySearchTreeTest()
  16.     {
  17.         BalancedBinarySearchTree<String> tree = new BalancedBinarySearchTree<>();
  18.         assertTrue(tree.check());
  19.         assertEquals(tree.size(), 0);
  20.         assertEquals(tree.put("aaa"), "aaa");
  21.         assertTrue(tree.check());
  22.         assertEquals(tree.size(), 1);
  23.         assertEquals(tree.put("bbb"), "bbb");
  24.         assertTrue(tree.check());
  25.         assertEquals(tree.size(), 2);
  26.         assertEquals(tree.put("ccc"), "ccc");
  27.         assertTrue(tree.check());
  28.         assertEquals(tree.size(), 3);
  29.         assertEquals(tree.put("ddd"), "ddd");
  30.         assertTrue(tree.check());
  31.         assertEquals(tree.size(), 4);
  32.         assertEquals(tree.put("eee"), "eee");
  33.         assertTrue(tree.check());
  34.         assertEquals(tree.size(), 5);
  35.         assertEquals(tree.put("xxx"), "xxx");
  36.         assertTrue(tree.check());
  37.         assertEquals(tree.size(), 6);
  38.         assertEquals(tree.put("yyy"), "yyy");
  39.         assertTrue(tree.check());
  40.         assertEquals(tree.size(), 7);
  41.         assertEquals(tree.put("zzz"), "zzz");
  42.         assertTrue(tree.check());
  43.         assertEquals(tree.size(), 8);
  44.         assertEquals(tree.put("iii"), "iii");
  45.         assertTrue(tree.check());
  46.         assertEquals(tree.size(), 9);
  47.         assertEquals(tree.put("jjj"), "jjj");
  48.         assertTrue(tree.check());
  49.         assertEquals(tree.size(), 10);
  50.         assertEquals(tree.find("aaa"), "aaa");
  51.         assertEquals(tree.find("bbb"), "bbb");
  52.         assertEquals(tree.find("ccc"), "ccc");
  53.         assertEquals(tree.find("ddd"), "ddd");
  54.         assertNull(tree.find("fff"));
  55.         try {
  56.             assertEquals(tree.remove("ccc"), "ccc");
  57.             assertEquals(tree.size(), 9);
  58.         } catch (Exception e)
  59.         {
  60.             fail("Shouldn't throw an exception!");
  61.         }
  62.         assertNull(tree.find("ccc"));
  63.         assertEquals(tree.find("aaa"), "aaa");
  64.         assertEquals(tree.find("bbb"), "bbb");
  65.         assertEquals(tree.find("ddd"), "ddd");
  66.     }
  67.  
  68.     @Test
  69.     public void BTreeMapTest() {
  70.         BTreeMap<String, String> map = new BTreeMap<>();
  71.         assertTrue(map.isEmpty());
  72.         assertEquals(map.size(), 0);
  73.         assertNull(map.get("test"));
  74.         assertEquals(map.put("aaa", "AAA"), "AAA");
  75.         assertEquals(map.size(), 1);
  76.         assertFalse(map.isEmpty());
  77.         assertEquals(map.get("aaa"), "AAA");
  78.         assertFalse(map.isEmpty());
  79.         assertEquals(map.remove("aaa"), "AAA");
  80.         assertEquals(map.size(), 0);
  81.         assertTrue(map.isEmpty());
  82.         assertEquals(map.put("aaa", "AAA"), "AAA");
  83.         assertEquals(map.size(), 1);
  84.         assertFalse(map.isEmpty());
  85.         assertEquals(map.put("bbb", "BBB"), "BBB");
  86.         assertEquals(map.size(), 2);
  87.         assertFalse(map.isEmpty());
  88.         assertEquals(map.put("ccc", "CCC"), "CCC");
  89.         assertEquals(map.size(), 3);
  90.         assertFalse(map.isEmpty());
  91.         assertEquals(map.put("ddd", "DDD"), "DDD");
  92.         assertEquals(map.size(), 4);
  93.         assertFalse(map.isEmpty());
  94.         assertEquals(map.put("eee", "EEE"), "EEE");
  95.         assertEquals(map.size(), 5);
  96.         assertFalse(map.isEmpty());
  97.         assertNull(map.get("fff"));
  98.         assertNull(map.remove("fff"));
  99.         assertEquals(map.get("aaa"), "AAA");
  100.         assertFalse(map.isEmpty());
  101.         assertEquals(map.get("bbb"), "BBB");
  102.         assertFalse(map.isEmpty());
  103.         assertEquals(map.get("ccc"), "CCC");
  104.         assertFalse(map.isEmpty());
  105.         assertEquals(map.get("ddd"), "DDD");
  106.         assertFalse(map.isEmpty());
  107.         assertEquals(map.get("eee"), "EEE");
  108.         assertFalse(map.isEmpty());
  109.         assertEquals("BBB", map.remove("bbb"));
  110.         assertFalse(map.isEmpty());
  111.         assertEquals("CCC", map.remove("ccc"));
  112.         assertFalse(map.isEmpty());
  113.         assertEquals(map.remove("ddd"), "DDD");
  114.         assertFalse(map.isEmpty());
  115.         assertEquals(map.remove("aaa"), "AAA");
  116.         assertFalse(map.isEmpty());
  117.         assertEquals(map.remove("eee"), "EEE");
  118.         assertTrue(map.isEmpty());
  119.         assertNull(map.get("fff"));
  120.         assertNull(map.remove("fff"));
  121.     }
  122. }
  123.  

Saludos

 

¿Te gustó el post? COMPARTILO!