Big O - Data Structures

Question 1

What is the time complexity of SEARCH for an ARRAY?

Answer 1

O(n) - okay

Question 2

What is the time complexity of INSERTION for an ARRAY?

Answer 2

O(n) - okay

Question 3

What is the time complexity of DELETION for an ARRAY?

Answer 3

O(n) - okay

Question 4

What is the worst space complexity of an array?

Answer 4

O(n) - okay

Question 5

What is the time complexity of ACCESS of a STACK?

Answer 5

O(n) - okay

Question 6

What is the time complexity of SEARCH of a STACK?

Answer 6

O(n) - okay

Question 7

What is the time complexity of INSERTION of a STACK?

Answer 7

O(1) - great

Question 8

What is the average time complexity of DELETION of a STACK?

Answer 8

O(1) - great

Question 9

What is the worst space complexity of a STACK?

Answer 9

O(n) - okay

Question 10

What is the time complexity of ACCESS of a LINKED LIST?

Answer 10

O(n) - okay

Question 11

What is the time complexity of SEARCH of a LINKED LIST?

Answer 11

O(n) - okay

Question 12

What is the time complexity of INSERTION of a LINKED LIST?

Answer 12

O(1) - great

Question 13

What is the time complexity of DELETION of a LINKED LIST?

Answer 13

O(1) - great

Question 14

What is the worst space complexity of a LINKED LIST?

Answer 14

O(n) - okay

Question 15

What is the average time complexity of access, search, insertion, and deletion of a SKIP LIST?

Answer 15

O(log(n)) - good

Question 16

What is the worst time complexity of access, search, insertion, and deletion of a SKIP LIST?

Answer 16

O(n) - okay

Question 17

What is the worst space complexity of a SKIP LIST?

Answer 17

O(n log(n)) - bad!

Question 18

What is the time complexity of ACCESS of a HASH TABLE?

Answer 18

Not applicable (why?)

Question 19

What is the average time complexity of SEARCH, INSERTION, and DELETION of a HASH TABLE?

Answer 19

O(1) - great!

Question 20

What is the worst time complexity of SEARCH, INSERTION, and DELETION of a HASH TABLE?

Answer 20

O(n) - okay

Question 21

What is the worst space complexity of a HASH TABLE?

Answer 21

O(n) - okay

Question 22

What is the average time complexity of access, search, insertion, and deletion of a BINARY SEARCH TREE?

Answer 22

O(log(n)) - good

Question 23

What is the worst time complexity of access, search, insertion, and deletion of a BINARY SEARCH TREE?

Answer 23

O(n) - okay

Question 24

What is the worst space complexity of a BINARY SEARH TREE?

Answer 24

O(n) - okay

Question 25

What is the average time complexity of ACCESS for a CARTESIAN TREE or a SPLAY TREE?

Answer 25

Not applicable (why?)

Question 26

What is the average time complexity of search, insertion and deletion for a CARTESIAN TREE?

Answer 26

O(log(n)) - good

Question 27

What is the worst time complexity of search, insertion and deletion for a CARTESIAN TREE?

Answer 27

O(n) - okay

Question 28

What is the worst space complexity of a CARTESIAN TREE?

Answer 28

O(n) - okay

Question 29

What is the time complexity of access, search, insertion and deletion for a B-TREE?

Answer 29

O(log(n)) - good

Question 30

What is the time complexity of access, search, insertion and deletion for a RED-BLACK TREE?

Answer 30

O(log(n)) - good

Question 31

What is the time complexity of search, insertion and deletion for a SPLAY TREE?

Answer 31

O(log(n)) - good

Question 32

What is the time complexity of access, search, insertion and deletion for a AVL TREE?

Answer 32

O(log(n)) - good

Question 33

What is the worst space complexity of a B-TREE?

Answer 33

O(n) - okay

Question 34

What is the worst space complexity of a RED-BLACK TREE?

Answer 34

O(n)- okay

Question 35

What is the worst space complexity of a SPLAY TREE?

Answer 35

O(n) - okay

Question 36

What is the worst space complexity of a AVL TREE?

Answer 36

O(n) - okay

Question 37

What is an array?

Answer 37

A simple data structure consisting of a collection of elements, identified by at least one array index or key. [3,5,6,8,2]

Question 38

What is a stack?

Answer 38

An abstracted data type which is an ordered collection of elements with two operations, push (adds) and pop(removes last added).

Question 39

What data structures can be used to implement a STACK?

Answer 39

Arrays or linked lists.

Question 40

What is a linked list?

Answer 40

A data structure consisting of a group of nodes which represent a sequence. Each node consists of data and reference to the next node.

Question 41

What are advantages of linked lists?

Answer 41

1. Dynamic data structure that allocates memory when needed 2. Insertion and deletion are easy to implement and FAST! 3. Can create stacks and queues easily. 4. Reduce access time and can expand in real time without memory overhead.

Question 42

What is a doubly linked list?

Answer 42

A linked list where each node contains a reference to the next and previous nodes, allowing forward and backward traversal.

Question 43

What is XOR-linking?

Answer 43

It uses bitwise XOR operation to compress the next and previous node address information into a single address field.

Question 44

What are some disadvantages of linked lists?

Answer 44

1. Uses more memory because of pointers needing to store next node info. 2. Nodes need to be read in order from beginning. 3. Nodes stored incontiguously (entries are not stored next to each other in memory), which increases time of access. 4. Reverse traversal of singly-linked lists is cumbersome, and double linked lists take up a lot of space.

Question 45

What is a skip list?

Answer 45

A data structure that allows fast search within an ordered sequence of elements. Can be implemented with parallel linked lists.

Question 46

What is a hash table?

Answer 46

A data structure that maps keys to values (dictionary, associative array). It uses a hash function that takes a value and assigns an index to it. Usually implemented with arrays.

Question 47

What is a binary search tree?

Answer 47

A family of data structures that stores items (numbers, names, etc) in memory in sorted order so look up can use binary search.

Question 48

What is a Cartesian tree?

Answer 48

A Cartesian tree is a tree data structure created from a set of data that obeys the following structural invariants:

1. The tree obeys in the min (or max) heap property – each node is less (or greater) than its children.
2. An inorder traversal of the nodes yields the values in the same order in which they appear in the initial sequence.
3. Cartesian Tree is not a height-balanced tree.
4. Cartesian tree of a sequence of distinct numbers is always unique.

Time Complexity :
At first look, the code seems to be taking O(n2) time as there are two loop in buildCartesianTree(). But actually, it takes O(NlogN) time in average and O(n^2) for sorted preorder traversal.

Auxiliary Space:
We declare a structure for every node as well as three extra arrays- leftchild[], rightchild[], parent[] to hold the indices of left-child, right-child, parent of each value in the input array. Hence the overall O(4*n) = O(n) extra space.

Application of Cartesian Tree

Cartesian Tree Sorting

A range minimum query on a sequence is equivalent to a lowest common ancestor query on the sequence’s Cartesian tree. Hence, RMQ may be reduced to LCA using the sequence’s Cartesian tree.

Treap, a balanced binary search tree structure, is a Cartesian tree of (key,priority) pairs; it is heap-ordered according to the priority values, and an inorder traversal gives the keys in sorted order.

Suffix tree of a string may be constructed from the suffix array and the longest common prefix array. The first step is to compute the Cartesian tree of the longest common prefix array.

Cartesian tree of a sequence of distinct numbers is always unique.
We will prove this using induction. As a base case, empty tree is always unique. For the inductive case, assume that for all trees containing n’ < n elements, there is a unique Cartesian tree for each sequence of n’ nodes. Now take any sequence of n elements. Because a Cartesian tree is a min-heap, the smallest element of the sequence must be the root of the Cartesian tree. Because an inorder traversal of the elements must yield the input sequence, we know that all nodes to the left of the min element must be in its left subtree and similarly for the nodes to the right. Since the left and right subtree are both Cartesian trees with at most n-1 elements in them (since the min element is at the root), by the induction hypothesis there is a unique Cartesian tree that could be the left or right subtree. Since all our decisions were forced, we end up with a unique tree, completing the induction.

**How to construct Cartesian Tree?**
A O(n2) solution for construction of Cartesian Tree is discussed here (Note that the above program here constructs the “special binary tree” (which is nothing but a Cartesian tree)

A O(nlogn) Algorithm :
It’s possible to build a Cartesian tree from a sequence of data in O(NlogN) time on average. Beginning with the empty tree,

Scan the given sequence from left to right adding new nodes as follows:

Position the node as the right child of the rightmost node.

Scan upward from the node’s parent up to the root of the tree until a node is found whose value is greater than the current value.

If such a node is found, set its right child to be the new node, and set the new node’s left child to be the previous right child.

If no such node is found, set the new child to be the root, and set the new node’s left child to be the previous tree.

Source: https://www.geeksforgeeks.org/cartesian-tree/

Question 49

What is a red-black tree?

Answer 49

A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the colour (red or black). These colours are used to ensure that the tree remains balanced during insertions and deletions. Although the balance of the tree is not perfect, it is good enough to reduce the searching time and maintain it around O(log n) time, where n is the total number of elements in the tree. This tree was invented in 1972 by Rudolf Bayer.

It must be noted that as each node requires only 1 bit of space to store the colour information, these types of trees show identical memory footprint to the classic (uncoloured) binary search tree.

Rules That Every Red-Black Tree Follows:

Every node has a colour either red or black.

The root of tree is always black.

There are no two adjacent red nodes (A red node cannot have a red parent or red child).

Every path from a node (including root) to any of its descendant NULL node has the same number of black nodes.

Why Red-Black Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(log n) after every insertion and deletion, then we can guarantee an upper bound of O(log n) for all these operations. The height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree.

Sr. No.AlgorithmTime Complexity

1. SearchO(log n)
2. InsertO(log n)
3. DeleteO(log n)

Comparison with AVL Tree:

The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves frequent insertions and deletions, then Red-Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over Red-Black Tree.

Source: https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/?ref=leftbar-rightbar

Question 50

What is a splay tree?

Answer 50

Summary

A self-adjusting binary search tree with the property that recently accessed elements are quick to access again, by reorganizing the accessed element to the root.

Definition

A Splay tree is a self-adjusting binary search tree invented by Sleator and Tarjan. Unlike an AVL tree (or a Red-Black tree), the structure of the splay tree changes even after the search operation. Every time we search an item x or insert x, it moves x to the root of the tree so that the next access of x is quick. The goal of the splay tree is not to make every operation fast rather make the sequence of operations fast. The individual operation in the splay tree can, sometimes, take O(n) time making the worst case running time linear. The sequence of operations, however, take O(logn) amortized time per operation. In other words, the sequence of M operations takes O(Mlogn)

time. Since the splay tree adjusts itself according to usage, it performs much more efficiently than other binary search trees if the usage pattern is skewed.

Unlike an AVL or a Red-Black tree where the tree must maintain their invariants all the time, the structure of the splay tree can be in any arbitrary state (although it should maintain the binary search tree invariants all the time) but during every operation, it restructures the tree to improve the efficiency of future (incoming) operations.

The splay tree moves a node x

to the root of the tree by performing series of single and double tree rotations. Each double rotations moves x to its grandparent’s place and every single rotation moves x to its parent’s place. We perform these rotations until x reaches to the root of the tree. This process is called splaying. Besides moving x to the root, splaying also shortens the height of the tree which makes the tree more balanced. There are two types of single rotations and four types of double rotations. Each of them is explained in detail below.

Zig Rotation

Zig is a single rotation. We do zig rotation on node x

if x is a left child and x does not have a grandparent (i.e. x’s parent is a root node). To make the zig rotation, we rotate x’s parent to the right. This is illustrated in figure 1.

Zag Rotation

Zag rotation is a mirror of zig rotation. We do zag rotation on node x

if x is a right child and x does not have a grandparent. To make the zag rotation, we perform a left rotation at x’s parent node. This is illustrated in figure 2.

Zig-Zig Rotation

Zig-Zig is a double rotation. We do a zig-zig rotation on x

when x is a left child and x’s parent node is also a left child. The zig-zig rotation is done by rotating x’s grandparent node to the right followed by right rotation at x’s parent node.

Zag-Zag Rotation

Zag-Zag rotation is a mirror of zig-zig rotation. We do zag-zag rotation on x

if x is a right child and x’s parent is also a right child. To make the zag-zag rotation, we first do a left rotation at x’s grandparent and then do the left rotation at x’s parent node. Figure 4 illustrates this.

Zig-Zag Rotation

Zig-zag rotation is also a double rotation. We perform zig-zag rotation on x

when x is a right child and x’s parent is a left child. Zig-zag rotation is done by doing a left rotation at x’s parent node followed by right rotating x grandparent (new parent) node. This is illustrated in figure 5.

Zag-Zig Rotation

The last rotation is the zag-zig rotation. It is a mirror of zig-zag rotation. To do zag-zig rotation on node x

, we do the right rotation at x’s parent node and left rotation at x grandparent (new parent) node. Figure 6 illustrates this.

Advantages and disadvantages of Splay Trees

Following are the advantages of splay trees over other binary search trees.

In an amortized sense, ignoring constant factors, they are never much worse than constrained structures, and since they adjust according to usage, they can be much more efficient if the usage pattern is skewed.

They need less space since no balance or other constraint information is stored.

Their access and update algorithms are conceptually simple and easy to implement.

Following are the disadvantages of splay trees.

They require more local adjustments, especially during accesses (look-up operations). (Explicitly constrained structures need adjusting only during updates, not during accesses.)

Individual operations within a sequence can be expensive, which may be a drawback in real-time applications.

Source: https://algorithmtutor.com/Data-Structures/Tree/Splay-Trees/

Question 51

What is an AVL tree?

Answer 51

Adelson-Velsky and Landis tree. Self balancing binary search tree that ensures the heights of two child subtrees of any node differ by at most one. Tree rotations rotate child and node to balance height and distribute children evenly.

Why AVL Trees?
Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree (See this video lecture for proof).

Source: https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

Question 52

What is the time complexity of ACCESS for an ARRAY?

Answer 52

O(1) - great