A BRIEF EXCURSION TO BINARY SEARCH AND BINARY TREE, A SHORT INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS
Data Structures & Algorithms
A data structure is: a particular way of storing and organizing data in a computer so that it can be used efficiently.
While an algorithm is: a step-by-step procedure for calculations.
A data structure is a specialized format for organizing and storing data. General data structure types include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.
Different types and specific examples of data structures can be, but not limited to, Array, Linked Lists, Stack, Queues, Trees, Graphs, Sets, and Hash Tables.
A data structure is the concrete implementation of an abstract data type (ADT). Even though these terms used fairly interchangeably, an ADT is more high-level description of the data relationship and a description of how that data may operated upon whereas a data structure has more information on how these things are defined and actually implemented.
In computer science, an abstract data type (ADT) is a mathematical model for data types, where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.
An algorithm is a set of steps to accomplish a task. For instance, you might have a morning algorithm, as a daily routine:
- Wake up
- Brush teeth
- Shower
- Eat breakfast
More algorithms could include:
- Compressing data
- Encryption
- Searching
- Finding directions
- any process that can be broken down into small repeatable steps, in general.
All in all, Algorithm is important in order to build up logic and data structure is important to use memory in effective way.
As one of the types of Data Structures, an Array class is a linear collection of elements, but there are other ways to represent collections and organize data.
Trees store data in a hierarchy of layers. An element, or node at each layer can have links to lower level nodes. One simple example is a file system:
* /
* Users
* yoonmi
* Desktop
* Documents
* Downloads
* shared
* Desktop
* Downloads
* System
* Library
The top-level node is called the root. Each node can hold a value: here the root holds /. The children of a node are the nodes one level deeper. The children of the Users node hold yoonmi and shared. The lowest level nodes (the ones with no children) are called leaves.
In general, nodes can have any number of children. In the special case of binary trees, nodes can have at most two children. These children are called the left and right children.
An array and a tree are two kinds of data structures. A data structure is a way of storing and organizing data in a computer so that it can be used efficiently. Depending on how you will use the data, different data structures may be appropriate.
There could be two different kinds of search, using tree (a specific type of graph in data structures): DFS (Depth First Search) and BFS (Breadth First Search).
Given a tree, we may wish to enumerate all the values held by nodes in the tree. For instance, we may wish to go through the files/folders of the tree and print each one.
One common way to traverse (i.e., visit all the nodes) a tree is depth first search. The nodes are numbered in the order that we visit them:
1
/ \
2 5
/ / \
3 6 9
/ / \
4 7 8
Each time, we try to visit the left child, if it exists and hasn’t been visited yet. If it has, we try to visit the right child, if it exists and hasn’t been visited yet. If all the children have been visited, then we move up one level and repeat.
Watch this animation to see the order that you want to visit nodes in the tree.
Breadth first search is an alternative to depth-first search.
1
/ \
2 3
/ / \
4 5 6
/ / \
7 8 9
Here we visit a node, then each of its children, then each of their children, etc. Watch this animation to see the order that you want to visit nodes in the tree.
An advantage of breadth-first search is that it considers shallower nodes before deeper ones.
DFS and BFS are algorithms. What’s the difference between an algorithm and a method? An algorithm is an idea, an unambiguous but unrealized process that solves a problem and which potentially could be written in any language. A method is the implementation, a conversion of an algorithm into Ruby code which can then be run.
An algorithm can be coded up in any language.
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — -
Linear search
The linear and binary algorithms are named as such to describe how long (time complexity) a search is going to take based on the size of the input that is being search. (Big O notation: O(n))
BINARY SEARCH
- Compare x with the middle element.
- If x matches with middle element, we return the mid index.
- Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recur for right half.
- Else (x is smaller) recur for the left half.
NUMBER GUESSING GAME
What is the difference between binary search and binary search tree?
binary search → an Algorithm to find the target (in sorted condition only); using the comparison tree as a way of implementation, sorted array can perform binary search
- A tree data structure
- Each node has up to 2 children
- The left subtree of a node contains only nodes with keys less than the node’s key
- The right subtree of a node contains only nodes with keys greater than the node’s key
- An algorithm that works on a sorted data structure (usually, but not necessarily, an array) and, at each step, looking at the value in the middle and recursing to either the left or the right, depending on whether the target value is smaller or greater than the value in the middle (or stopping if it’s equal).
Binary Tree
A binary tree is a tree where each node can have a maximum of two children. By convention, these are referred to as the left child and the right child. These children are themselves the roots of the left subtree and the right subtree.
A binary tree is a collection of nodes where each node has between zero and two children. Put simply, each node has a value, left child, and a right child. Where a node does not have a left or right child, the node should point to nil. The root of this tree has value 5.
Binary Tree:
5
/ \
7 9
\ / \
8 1 4
/ \ \
3 4 9
Binary Search Tree
A binary search tree is a binary tree with the additional rule that, given a node with a value v, the nodes in its left subtree are all less than v and those in the right subtree are greater than [or equal to] v.
Notice in the image that this is also true in the subtrees. While 6 is less than 8 and in the root’s left subtree, because it is greater than 3, it is in that node’s right subtree.
A binary search tree is a binary tree with the following additional properties:
- The left subtree of a node contains only nodes with values less than the node’s value.
- The right subtree of a node contains only nodes with values greater than or equal to the node’s value.
- The left and right subtree each must also be a binary search tree.
Binary Search Tree:
8
/ \
3 10
/ \ / \
1 6 9 12
/ \ /
4 7 11
—
A key thing to remember here is that while a node might be the child of one node, it may have children for which it is the root.
Binary Search Tree Methods
- add(value)
- contains(value)
- find_biggest() / find_smallest()
- depth_first_list() * — list the values in order from smallest to largest. The above example would return 1, 3, 4, 6, 7, 8, 9, 10, 11, 12.
- breadth_first_list() * — list the elements level by level. Starting at the root, read the values left to right and then move down to the next level. So the above would return 8, 3, 10, 1, 6, 9, 12, 4, 7, 11.
- delete_node() **
- self.create() — creates a BST based on an array.
Binary Search Trees
What are the benefits of a binary search tree?
Both in terms of lookup and insertion, a BST takes an average of Θ(log n). The worst case is O(n) because you could have inserted values in a strictly increasing or decreasing value.
Binary Search ← → Linear Search
Worst Case o(log n) ← → O(n)
Best Case o(1) ← → O(1)
Binary Search Trees
A node in a binary tree is a data structure that has an element, and a reference to two other binary trees, typically called the left and right subtrees. I.e., a node presents an interface like this:
Node:
element (an element of some type)
left (a binary tree, or NULL)
right (a binary tree, or NULL)
A binary search tree is a binary tree (i.e., a node, typically called the root) with the property that the left and right subtrees are also binary search trees, and that all the elements of all the nodes in the left subtree are less than the root’s element, and all the elements of all the nodes in the right subtree are greater than the root’s element. E.g.,
Binary Search
Binary search is an algorithm for finding an element in binary search tree. (It’s often expressed as a way of searching an ordered collection, and this is an equivalent description. I’ll describe the equivalence afterward.) It’s this:
search( element, tree ) {
if ( tree == NULL ) { return NOT_FOUND
} else if ( element == tree.element ) {
return FOUND_IT
} else if ( element < tree.element ) {
return search( element, tree.left )
} else { return search( element, tree.right )
}
}
This is typically an efficient method of search because at each step, you can remove half the search space. Of course, if you have a poorly balanced binary search tree, it can be inefficient (it can degrade to linear search). For instance, it has poor performance in a tree like:
3 — 4 — 5 — 6
Binary Search on Arrays
Binary search is often presented as a search method for sorted arrays. This does not contradict the description above. In fact, what it highlights the fact that we don’t actually care how a binary search tree is implemented; we just care that we can take an object and do three things with it: get a element, get a left sub-object, and get a right sub-object (subject, of course, to the constraints about the elements in the left being less than the element, and the elements in the right being greater, etc.).
We can do all three things with a sorted array. With a sorted array, the “element” is the middle element of the array, the left sub-object is the subarray to the left of it, and the right sub-object is the subarray to the right of it. E.g., the array
[1 3 4 5 7 8 11]
corresponds to the tree:
5
/ \
3 8
/ \ / \
1 4 7 11
Thus, we can write a binary search method for arrays like this:
search( element, array, begin, end ) {
if ( end <= begin ) { return NOT_FOUND
} else { midpoint = begin+(end-begin)/2 a_element = array[midpoint]
if ( element == midpoint ) {
return FOUND_IT
} else if ( element < midpoint ) {
return search( element, array, begin, midpoint )
} else {
return search( element, array, midpoint, end )
}
}
}
Conclusion
As often presented, binary search refers to the array based algorithm presented here, and binary search tree refers to a tree based data structure with certain properties. However, the properties that binary search requires and the properties that binary search trees have make these two sides of the same coin. Being a binary search tree often implies a particular implementation, but really it’s a matter of providing certain operations and satisfying certain constraints. Binary search is an algorithm that functions on data structures that have these operations and meet these constraints.
Pair Sum
Given a sorted array and a number, return true if any pairs of numbers in the array that sum to that number, else return false.
https://www.geeksforgeeks.org/two-pointers-technique/
https://stackoverflow.com/questions/21586085/difference-between-binary-search-and-binary-search-tree
