Posts

AVL tree vs RB tree with applications

-
Image
  AVL tree vs RB tree with applications   What is AVL Tree? In 1962, GM Adelson - Velsky and EM Landis invented the AVL Tree. The tree is named AVL after its creators. The AVL Tree is a height balanced binary search tree in which each node has a balance factor that is calculated by subtracting the height of its right sub-tree from the height of its left sub-tree. If the balance factor of each node is between -1 and 1, the tree is said to be balanced; otherwise, the tree is unbalanced and must be balanced. Balance Factor (k) = height (left(k)) - height (right(k)) If balance factor of any node is 1, it means that the left sub-tree is one level higher than the right sub-tree. If balance factor of any node is 0, it means that the left sub-tree and right sub-tree contain equal height. If balance factor of any node is -1, it means that the left sub-tree is one level lower than the right sub-tree. The figure below depicts an AVL tree. We can see that the balance...
27 comments
Read more
-
Image
         Finite Automata History of Finite Automata: The fact that finite automata has become a discipline of computer science demonstrates the breadth of its applications. A group of biologists, psychologists, mathematicians, engineers, and some of the first computer scientists were among the first to examine the concept of a finite state machine. The members of this group had a common interest in modelling human mental processes, whether in the brain or on a computer. Warren McCulloch and Walter Pitts, two neurophysiologists, were the first to describe finite automata in 1943. Their research paper, "A Logical Calculus Immanent in Nervous Activity," contributed significantly to the fields of neural network theory, automata theory, computation theory, and cybernetics. Later on in this study, G.H. Mealy and E.F. Theory of Automata Theoretical computer science and mathematics combine to form the theory of automata. It is the study of abstract machines and the issu...
26 comments
Read more