DSA Array Implementation
Array Implementation of Binary Trees
Just as Binary Trees are implemented before this point, it is helpful to implement Binary Trees using pointers from one element to the next, especially when the Binary Tree is modified frequently, to minimize the cost of all the memory shifts that we obtain from utilizing Arrays.
However, an Array implementation of a Binary Tree may make sense if we read from the Binary Tree much more often than we edit it. This is because an Array implementation may use less memory, be simpler to design, and, because of cache proximity, may be faster for some operations.
Cache locality refers to the storage of recently accessed memory by the computer’s fast cache memory or memory that is stored in the cache near the address being accessed at that moment. This occurs because the CPU most likely requires something in the following cycle that is similar to what it utilized in the preceding cycle, either in terms of time or space.
Computers can occasionally read from arrays more quickly because the next element is already cached and ready for quick access in case the CPU requires it in the upcoming cycle. This is because array items are stored consecutively in memory, one element after the other.
A more thorough explanation of array storage in memory may be found here.
Take a look at this Binary Tree:
==== example mukavu ====
This Binary Tree can be stored in an Array starting with the root node R on index 0. The rest of the tree can be built by taking a node stored on index i, and storing its left child node on index 2i+1, and its right child node on index 2⋅i+2.
Below is an Array implementation of the Binary Tree.
Example
Python:
binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F', None, None, None, None, None, None, 'G']
def left_child_index(index):
return 2 * index + 1
def right_child_index(index):
return 2 * index + 2
def get_data(index):
if 0 <= index < len(binary_tree_array):
return binary_tree_array[index]
return None
right_child = right_child_index(0)
left_child_of_right_child = left_child_index(right_child)
data = get_data(left_child_of_right_child)
print("root.right.left.data:", data)
Since the Binary Tree nodes in this version are stored in an array, a large portion of the code deals with using indexes to access nodes and determining which indexes to use.
Let’s say we want to find the left and right child nodes of node B. Because B is on index 2, B’s left child is on index 2⋅2+1=5, which is node E, right? And B’s right child is on index 2⋅2+2=6, which is node F, and that also fits with the drawing above, right?
Line 1 illustrates that this implementation calls for empty array members in cases where nodes have no children. Therefore, Binary Trees saved using Array implementation should be “perfect” Binary Trees, or almost perfect, to prevent wasting space on empty Array components.
Every internal node in a perfect binary tree has precisely two child nodes, and every leaf node is on the same level.
The Binary Tree above looks like this if the G node is removed:
==== example mukavu ====
Moreover, the following code can be expressed in its entirety without wasting any space on empty Array elements:
binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F']
The three distinct DFS traversals on an Array implementation of a Binary Tree can be carried out in this manner.
Example
Python:
binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F', None, None, None, None, None, None, 'G']
def left_child_index(index):
return 2 * index + 1
def right_child_index(index):
return 2 * index + 2
def pre_order(index):
if index >= len(binary_tree_array) or binary_tree_array[index] is None:
return []
return [binary_tree_array[index]] + pre_order(left_child_index(index)) + pre_order(right_child_index(index))
def in_order(index):
if index >= len(binary_tree_array) or binary_tree_array[index] is None:
return []
return in_order(left_child_index(index)) + [binary_tree_array[index]] + in_order(right_child_index(index))
def post_order(index):
if index >= len(binary_tree_array) or binary_tree_array[index] is None:
return []
return post_order(left_child_index(index)) + post_order(right_child_index(index)) + [binary_tree_array[index]]
print("Pre-order Traversal:", pre_order(0))
print("In-order Traversal:", in_order(0))
print("Post-order Traversal:", post_order(0))
