Skip to main content

Picking the structure!!

Use of arrays, rather sorted arrays or a linked list is somewhat difficult because both have their pros and cons. 

Arrays excel when we have to perform a binary search while it’s faster to add and remove elements from linked lists. 

A tree is one structure where there is ONLY ONE path to reach to a node. This can be explained further as “Nodes cannot be in closed loop”. Also there is a hierarchical relationship of parent and child.

The average complexity varies from logarithmic to linear time.
Now coming further to a data structure BSTs aka Binary Search Trees. Points to be remembered here:-
  1. Maximum two children.
  2. Left child is smaller than parent.
  3. Right one is greater than parent.



Traversals:-
 
In order Traversal
Ascending Sort; left subtree + root+ right subtree. So the above tree will look like:  4, 12, 16, 25, 28, 32

Pre order Traversal
Root + left subtree + right subtree recursively. Eg: 25, 12, 4, 16, 32, 28

Post Order Traversal (left, right, root)
Eg: 4, 16, 12, 28, 32, 25


Height of tree is given by formula 2(h-1)

Deletion in a tree:-
There lies 3 cases:-
  1. When node to be deleted is a leaf node. 
  2. The node has a single child. 
  3. The node has two children. In this case find the predecessor or successor of that particular node, which is Greatest node in the Left subtree or Smallest node in the Right subtree. Replace the concerned node with any of the two.


Labels:

Comments

Post a Comment

Popular posts from this blog

Appian UUID vs ID

IDs in Appian:- There are 2 kinds of IDs which are observed in Appian namely UUIDs and IDs. Let’s go through them briefly.  Many of the functionalities are covered by Smart Services hence the explicit use of Ids are reduced or those can be done by relational database entries in some special cases. Sources: Appian Documentation Appian Community
Post a Comment
Read more

Appian function merge()

Lets have a look at merge() function . It takes a number of list and combines them to create a new list. Takes an element sequentially from each list and append it to the major list. Below are some of the examples. merge({ 10 , 50 }, { 60 , 40 }) Value 10 ; 60 ; 50 ; 40 merge({ 10 , 30 }, { 20 , 40 , 50 }) Value 10 ; 20 ; 30 ; 40 ; ; 50 merge({ 10 , 30 }, { 20 , 40 , 50 }, { 60 }) Value 10 ; 20 ; 60 ; 30 ; 40 ; ; ; 50 ; #After the last semicolon one elelent exist merge({ 10 , 30 }, { 20 , 40 , 50 }, { 60 , 70 , 80 }) Value 10 ; 20 ; 60 ; 30 ; 40 ; 70 ; ; 50 ; 80 merge({ 1 , 2 , 3 }, { 4 , 5 , 6 }) returns 1 , 4 , 2 , 5 , 3 , 6 Source
Post a Comment
Read more

Simple Queue Implementation using Python

Stacks and Queues are not data structures, they are basically abstract data types. The simple data structure can be an array or a linked list. Queues are FIFO.. First In and First Out. Queues do have real world operations like:- 1.    Token System 2.    Organising data to archive based on age. 3.    Scheduling 4.    Any task which involves first come first serve basis. Below is a simple implementation of Queue using Python. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Queue : def __init__ ( self ): self . queue = [] def isEmpty ( self ): return self . queue == [] def enqueue ( self , data): self . queue . append(data) def dequeue ( self ): data = self . queue[ 0 ] del self . queue[ 0 ] return data def peek ( self ): return se...
Post a Comment
Read more