A Graph is a non-linear data structure that consists of vertices (nodes) and edges.

A vertex, also called a node, is a point or an object in the Graph, and an edge is used to connect two vertices with each other.

Graphs are non-linear because the data structure allows us to have different paths to get from one vertex to another, unlike with linear data structures like Arrays or Linked Lists.

Graphs are used to represent and solve problems where the data consists of objects and relationships between them

Examples:

Social Networks: Each person is a vertex, and relationships (like friendships) are the edges. Algorithms can suggest potential friends.

Maps and Navigation: Locations, like a town or bus stops, are stored as vertices, and roads are stored as edges. Algorithms can find the shortest route between two locations when stored as a Graph.

Internet: Can be represented as a Graph, with web pages as vertices and hyperlinks as edges.

Biology: Graphs can model systems like neural networks or the spread of diseases.

வரைபடம் (கிராஃப்)

ஒரு வரைபடம் என்பது உச்சிகள் (முனைகள்) மற்றும் விளிம்புகளைக் கொண்ட ஒரு நேரியல் அல்லாத தரவுக் கட்டமைப்பாகும்.

முனை என்றும் அழைக்கப்படும் ஒரு உச்சி, வரைபடத்தில் உள்ள ஒரு புள்ளி அல்லது ஒரு பொருளாகும், மேலும் இரண்டு உச்சிகளை ஒன்றோடொன்று இணைக்க ஒரு விளிம்பு பயன்படுத்தப்படுகிறது.

அணிகள் அல்லது இணைக்கப்பட்ட பட்டியல்கள் போன்ற நேரியல் தரவுக் கட்டமைப்புகளைப் போலல்லாமல், ஒரு உச்சியிலிருந்து மற்றொரு உச்சிக்குச் செல்ல வெவ்வேறு பாதைகளை இந்தத் தரவுக் கட்டமைப்பு அனுமதிப்பதால், வரைபடங்கள் நேரியல் அல்லாதவை ஆகும்.

தரவு என்பது பொருட்களையும் அவற்றுக்கிடையேயான உறவுகளையும் கொண்டிருக்கும் சிக்கல்களைப் பிரதிநிதித்துவப்படுத்தவும் தீர்க்கவும் வரைபடங்கள் பயன்படுத்தப்படுகின்றன.

உதாரணங்கள்:

சமூக வலைப்பின்னல்கள்: ஒவ்வொரு நபரும் ஒரு உச்சியாகவும், உறவுகள் (நட்புகள் போன்றவை) விளிம்புகளாகவும் உள்ளன. வழிமுறைகள் சாத்தியமான நண்பர்களைப் பரிந்துரைக்க முடியும்.

வரைபடங்கள் மற்றும் வழிசெலுத்தல்: ஒரு நகரம் அல்லது பேருந்து நிறுத்தங்கள் போன்ற இடங்கள் உச்சிகளாகவும், சாலைகள் விளிம்புகளாகவும் சேமிக்கப்படுகின்றன. ஒரு வரைபடமாகச் சேமிக்கப்படும்போது, ​​இரண்டு இடங்களுக்கு இடையே உள்ள குறுகிய வழியை வழிமுறைகள் கண்டறிய முடியும்.

இணையம்: வலைப்பக்கங்களை உச்சிகளாகவும், ஹைப்பர்லிங்குகளை விளிம்புகளாகவும் கொண்டு இணையத்தை ஒரு வரைபடமாகப் பிரதிநிதித்துவப்படுத்தலாம்.

உயிரியல்: நரம்பு மண்டலங்கள் அல்லது நோய்கள் பரவுதல் போன்ற அமைப்புகளை வரைபடங்கள் மூலம் மாதிரியாக்கலாம்.

Graph Properties

A weighted Graph is a Graph where the edges have values. The weight value of an edge can represent things like distance, capacity, time, or probability.

A connected Graph is when all the vertices are connected through edges somehow. A Graph that is not connected, is a Graph with isolated (disjoint) subgraphs, or single isolated vertices.

A directed Graph, also known as a digraph, is when the edges between the vertex pairs have a direction. The direction of an edge can represent things like hierarchy or flow.

A cyclic Graph is defined differently depending on whether it is directed or not:

A directed cyclic Graph is when you can follow a path along the directed edges that goes in circles. Removing the directed edge from Apple to Coffee in the animation above makes the directed Graph not cyclic anymore.

An undirected cyclic Graph is when you can come back to the same vertex you started at without using the same edge more than once. The undirected Graph above is cyclic because we can start and end up in vertes Coffee without using the same edge twice.

A loop, also called a self-loop, is an edge that begins and ends on the same vertex. A loop is a cycle that only consists of one edge. By adding the loop on vertex Apple in the animation above, the Graph becomes cyclic.

வரைபடப் பண்புகள்

எடைகொண்ட வரைபடம் என்பது விளிம்புகள் மதிப்புகளைக் கொண்ட ஒரு வரைபடமாகும். ஒரு விளிம்பின் எடை மதிப்பு தூரம், கொள்ளளவு, நேரம் அல்லது நிகழ்தகவு போன்ற விஷயங்களைக் குறிக்கலாம்.

இணைக்கப்பட்ட வரைபடம் என்பது அனைத்து முனைகளும் ஏதேனும் ஒரு வகையில் விளிம்புகள் வழியாக இணைக்கப்பட்டிருக்கும் நிலையாகும். இணைக்கப்படாத வரைபடம் என்பது தனிமைப்படுத்தப்பட்ட (தொடர்பற்ற) துணை வரைபடங்கள் அல்லது தனித்தனி முனைகளைக் கொண்ட ஒரு வரைபடமாகும்.

திசையிடப்பட்ட வரைபடம், இது டைகிராஃப் என்றும் அழைக்கப்படுகிறது, என்பது முனை ஜோடிகளுக்கு இடையிலான விளிம்புகள் ஒரு திசையைக் கொண்டிருக்கும் நிலையாகும். ஒரு விளிம்பின் திசையானது படிநிலை அல்லது ஓட்டம் போன்ற விஷயங்களைக் குறிக்கலாம்.

ஒரு சுழற்சி வரைபடம் என்பது அது திசையிடப்பட்டதா இல்லையா என்பதைப் பொறுத்து வித்தியாசமாக வரையறுக்கப்படுகிறது:

ஒரு திசையிடப்பட்ட சுழற்சி வரைபடம் என்பது, திசையிடப்பட்ட விளிம்புகள் வழியாக வட்டமாகச் செல்லும் ஒரு பாதையைப் பின்பற்ற முடிந்தால் ஆகும். மேலே உள்ள அசைவூட்டத்தில் ஆப்பிளிலிருந்து காபிக்குச் செல்லும் திசையிடப்பட்ட விளிம்பை நீக்குவது, அந்த திசையிடப்பட்ட வரைபடத்தை இனி சுழற்சி அற்றதாக ஆக்குகிறது.

ஒரு திசையிடப்படாத சுழற்சி வரைபடம் என்பது, ஒரே விளிம்பை ஒன்றுக்கு மேற்பட்ட முறை பயன்படுத்தாமல், நீங்கள் தொடங்கிய அதே முனைக்குத் திரும்ப முடிந்தால் ஆகும். மேலே உள்ள திசையிடப்படாத வரைபடம் சுழற்சி கொண்டது, ஏனெனில் நாம் ஒரே விளிம்பை இருமுறை பயன்படுத்தாமல் காபி முனையில் தொடங்கி அங்கேயே முடிக்க முடியும்.

ஒரு கண்ணி, இது சுய-கண்ணி என்றும் அழைக்கப்படுகிறது, என்பது ஒரே முனையில் தொடங்கி முடிவடையும் ஒரு விளிம்பாகும். ஒரு கண்ணி என்பது ஒரே ஒரு விளிம்பைக் கொண்ட ஒரு சுழற்சியாகும். மேலே உள்ள அசைவூட்டத்தில் ஆப்பிள் முனையில் கண்ணியைச் சேர்ப்பதன் மூலம், அந்த வரைபடம் சுழற்சி கொண்டதாகிறது.

Graph Representations

A Graph representation tells us how a Graph is stored in memory.

Different Graph representations can:

• take up more or less space.
• be faster or slower to search or manipulate.
• be better suited depending on what type of Graph we have (weighted, directed, etc.), and what we want to do with the Graph.
• be easier to understand and implement than others.

Graph representations store information about which vertices are adjacent, and how the edges between the vertices are. Graph representations are slightly different if the edges are directed or weighted.

Two vertices are adjacent, or neighbors, if there is an edge between them.

வரைபடப் பிரதிநிதித்துவங்கள்

ஒரு வரைபடம் நினைவகத்தில் எவ்வாறு சேமிக்கப்படுகிறது என்பதை வரைபடப் பிரதிநிதித்துவம் நமக்குச் சொல்கிறது.

வெவ்வேறு வரைபடப் பிரதிநிதித்துவங்கள்:

• அதிகமாகவோ அல்லது குறைவாகவோ இடத்தை எடுத்துக் கொள்ளலாம்.
• தேட அல்லது கையாள வேகமாகவோ அல்லது மெதுவாகவோ இருக்கலாம்.
• நம்மிடம் உள்ள வரைபட வகை (எடையிடப்பட்டது, இயக்கப்பட்டது போன்றவை) மற்றும் வரைபடத்துடன் நாம் என்ன செய்ய விரும்புகிறோம் என்பதைப் பொறுத்து சிறப்பாகப் பொருந்தலாம்.
• மற்றவற்றை விட புரிந்துகொள்வதற்கும் செயல்படுத்துவதற்கும் எளிதாக இருக்கும்.

வரைபடப் பிரதிநிதித்துவங்கள் எந்த முனைகள் அருகில் உள்ளன, மற்றும் முனைகளுக்கு இடையிலான விளிம்புகள் எவ்வாறு உள்ளன என்பது பற்றிய தகவல்களைச் சேமிக்கின்றன. விளிம்புகள் இயக்கப்பட்டாலோ அல்லது எடையிடப்பட்டாலோ வரைபடப் பிரதிநிதித்துவங்கள் சற்று வித்தியாசமாக இருக்கும்.

இரண்டு முனைகள் அருகில் உள்ளன, அல்லது அவற்றுக்கிடையே ஒரு விளிம்பு இருந்தால், அண்டை வீட்டாராக இருக்கும்.

Adjacency Matrix Graph Representation

Adjacency Matrix is the Graph representation (structure) we will use for this tutorial.

The Adjacency Matrix is a 2D array (matrix) where each cell on index (i,j) stores information about the edge from vertex i to vertex j.

Below is a Graph with the Adjacency Matrix representation next to it.

அண்மை அணி வரைபடப் பிரதிநிதித்துவம்

இந்த டுடோரியலுக்காக நாம் பயன்படுத்தப் போகும் வரைபடப் பிரதிநிதித்துவம் (அமைப்பு) அண்மை அணி ஆகும்.

அண்மை அணி என்பது ஒரு 2D அணி (மேட்ரிக்ஸ்) ஆகும், இதில் (i,j) குறியீட்டில் உள்ள ஒவ்வொரு கலமும், i முனையிலிருந்து j முனைக்குச் செல்லும் விளிம்பைப் பற்றிய தகவல்களைச் சேமிக்கிறது.

கீழே ஒரு வரைபடமும், அதற்கு அருகில் அதன் அண்மை அணிப் பிரதிநிதித்துவமும் கொடுக்கப்பட்டுள்ளது.

An undirected Graph and the adjacency matrix

The adjacency matrix above represents an undirected Graph, so the values ‘1’ only tells us where the edges are. Also, the values in the adjacency matrix is symmetrical because the edges go both ways (undirected Graph).

திசையற்ற வரைபடம் மற்றும் அண்மை அணி

மேலே உள்ள அண்மை அணியானது ஒரு திசையற்ற வரைபடத்தைக் குறிக்கிறது, எனவே ‘1’ என்ற மதிப்புகள் விளிம்புகள் எங்கு அமைந்துள்ளன என்பதை மட்டுமே நமக்குத் தெரிவிக்கின்றன. மேலும், இது ஒரு திசையற்ற வரைபடம் என்பதால், விளிம்புகள் இரு வழிகளிலும் செல்வதால், அண்மை அணியில் உள்ள மதிப்புகள் சமச்சீராக உள்ளன.

Below is a directed and weighted Graph with the Adjacency Matrix representation next to it.

A directed and weighted Graph,and its adjacency matrix.

In the adjacency matrix above, the value 3 on index (0,1) tells us there is an edge from vertex Apple to vertex Bread, and the weight for that edge is 3.

As you can see, the weights are placed directly into the adjacency matrix for the correct edge, and for a directed Graph, the adjacency matrix does not have to be symmetric.

Adjacency List Graph Representation

In case we have a ‘sparse’ Graph with many vertices, we can save space by using an Adjacency List compared to using an Adjacency Matrix, because an Adjacency Matrix would reserve a lot of memory on empty Array elements for edges that don’t exist.

A ‘sparse’ Graph is a Graph where each vertex only has edges to a small portion of the other vertices in the Graph.

An Adjacency List has an array that contains all the vertices in the Graph, and each vertex has a Linked List (or Array) with the vertex’s edges.

அண்மைப் பட்டியல் வரைபடப் பிரதிநிதித்துவம்

பல முனைகளைக் கொண்ட ஒரு ‘அடர்த்தி குறைந்த’ வரைபடம் நம்மிடம் இருக்கும் பட்சத்தில், அண்மை அணிக்குப் பதிலாக அண்மைப் பட்டியலைப் பயன்படுத்துவதன் மூலம் நாம் நினைவக இடத்தை மிச்சப்படுத்தலாம். ஏனெனில், அண்மை அணியானது இல்லாத விளிம்புகளுக்கான காலி அணி உறுப்புகளுக்கு அதிக நினைவகத்தை ஒதுக்கும்.

ஒரு ‘அடர்த்தி குறைந்த’ வரைபடம் என்பது, அதில் உள்ள ஒவ்வொரு முனையும், வரைபடத்தில் உள்ள மற்ற முனைகளில் ஒரு சிறிய பகுதிக்கு மட்டுமே விளிம்புகளைக் கொண்டிருக்கும் ஒரு வரைபடமாகும்.

ஒரு அண்மைப் பட்டியலில், வரைபடத்தில் உள்ள அனைத்து முனைகளையும் கொண்ட ஒரு அணி இருக்கும், மேலும் ஒவ்வொரு முனையும் அந்த முனையின் விளிம்புகளைக் கொண்ட ஒரு இணைக்கப்பட்ட பட்டியலைக் (அல்லது அணியைக்) கொண்டிருக்கும்.

In the adjacency list above, the vertices Apple to Dosa are placed in an Array, and each vertex in the array has its index written right next to it.

Each vertex in the Array has a pointer to a Linked List that represents that vertex’s edges. More specifically, the Linked List contains the indexes to the adjacent (neighbor) vertices.

So for example, vertex Apple has a link to a Linked List with values 3, 1, and 2. These values are the indexes to Apple’s adjacent vertices Dosa, Bread, and Coffee.

மேலே உள்ள அண்மைப் பட்டியலில், ஆப்பிள் முதல் தோசை வரையிலான முனைகள் ஒரு வரிசையில் (அரேயில்) வைக்கப்பட்டுள்ளன, மேலும் அந்த வரிசையில் உள்ள ஒவ்வொரு முனைக்கும் அதன் குறியீட்டு எண் அதற்கு நேராகவே எழுதப்பட்டுள்ளது.

அந்த வரிசையில் உள்ள ஒவ்வொரு முனைக்கும், அந்த முனையின் விளிம்புகளைக் குறிக்கும் ஒரு இணைக்கப்பட்ட பட்டியலுக்கான சுட்டிக்காட்டி (pointer) உள்ளது. இன்னும் குறிப்பாகச் சொன்னால், அந்த இணைக்கப்பட்ட பட்டியலில், அருகிலுள்ள (அண்டை) முனைகளின் குறியீட்டு எண்கள் உள்ளன.

உதாரணமாக, ஆப்பிள் என்ற முனைக்கு 3, 1, மற்றும் 2 ஆகிய மதிப்புகளைக் கொண்ட ஒரு இணைக்கப்பட்ட பட்டியலுக்கான இணைப்பு உள்ளது. இந்த மதிப்புகள், ஆப்பிளின் அண்டை முனைகளான தோசை, பிரெட் மற்றும் காபி ஆகியவற்றின் குறியீட்டு எண்களாகும்.

An Adjacency List can also represent a directed and weighted Graph, like this:

A directed and weighted Graph and its adjacency list.

In the Adjacency List above, vertices are stored in an Array. Each vertex has a pointer to a Linked List with edges stored as i,w, where i is the index of the vertex the edge goes to, and w is the weight of that edge.

Node ‘Dosa’ for example, has a pointer to a Linked List with an edge to vertex ‘Apple’. The values 0,4 means that vertex ‘Dosa’ has an edge to vertex on index 0 (vertex ‘Apple’), and the weight of that edge is 4.

ஒரு திசை மற்றும் எடை கொண்ட வரைபடத்தையும் (directed and weighted Graph) ஒரு அண்மைப் பட்டியல் மூலம் இவ்வாறு குறிப்பிடலாம்:

ஒரு திசை மற்றும் எடை கொண்ட வரைபடம் மற்றும் அதன் அண்மைப் பட்டியல்.

மேலே உள்ள அண்மைப் பட்டியலில், முனைகள் ஒரு வரிசையில் சேமிக்கப்பட்டுள்ளன. ஒவ்வொரு முனைக்கும் ஒரு இணைக்கப்பட்ட பட்டியலுக்கான சுட்டிக்காட்டி உள்ளது. அந்தப் பட்டியலில் விளிம்புகள் i,w என சேமிக்கப்பட்டுள்ளன, இங்கு i என்பது அந்த விளிம்பு செல்லும் முனையின் குறியீடு, மற்றும் w என்பது அந்த விளிம்பின் எடை ஆகும்.

உதாரணமாக, ‘Dosa’ என்ற முனை, ‘Apple’ என்ற முனைக்குச் செல்லும் ஒரு விளிம்பைக் கொண்ட இணைக்கப்பட்ட பட்டியலுக்கான ஒரு சுட்டிக்காட்டியைக் கொண்டுள்ளது. 0,4 என்ற மதிப்புகள், ‘Dosa’ என்ற முனையிலிருந்து குறியீடு 0-இல் உள்ள முனைக்கு (‘Apple’ என்ற முனைக்கு) ஒரு விளிம்பு உள்ளது என்பதையும், அந்த விளிம்பின் எடை 4 என்பதையும் குறிக்கிறது.

Graphs Implementation

To implement a Graph we will use an Adjacency Matrix, like the one below.

ஒரு வரைபடத்தை (Graph) செயல்படுத்த, கீழே உள்ளதைப் போன்ற ஒரு அண்மை அணி (Adjacency Matrix) பயன்படுத்தப்படும்.

To store data for each vertex, in this case the letters Apple, Bread, Coffee, and Dosa, the data is put in a separate array that matches the indexes in the adjacency matrix, like this:

For an undirected and not weighted Graph, like in the image above, an edge between vertices i and j is stored with value 1. It is stored as 1 on both places (j,i) and (i,j) because the edge goes in both directions. As you can see, the matrix becomes diagonally symmetric for such undirected Graphs.

Let’s look at something more specific. In the adjacency matrix above, vertex ‘Apple’ is on index 0, and vertex ‘Dosa’ is on index 3, so we get the edge between ‘Apple’ and ‘Dosa’ stored as value 1 in position (0,3) and (3,0), because the edge goes in both directions.

ஒவ்வொரு முனைப்புள்ளிக்குமான தரவைச் சேமிக்க, இந்தச் சந்தர்ப்பத்தில் ஆப்பிள், பிரெட், காபி மற்றும் தோசை ஆகிய வார்த்தைகளை, அருகாமை அணிவரிசையில் உள்ள குறியீடுகளுடன் பொருந்தக்கூடிய ஒரு தனி வரிசையில் தரவு வைக்கப்படுகிறது, இது பின்வருமாறு:

மேலே உள்ள படத்தில் உள்ளதைப் போன்ற திசையற்ற மற்றும் எடையற்ற வரைபடத்திற்கு, i மற்றும் j ஆகிய முனைப்புள்ளிகளுக்கு இடையிலான ஒரு விளிம்பு 1 என்ற மதிப்புடன் சேமிக்கப்படுகிறது. அந்த விளிம்பு இரு திசைகளிலும் செல்வதால், அது (j,i) மற்றும் (i,j) ஆகிய இரண்டு இடங்களிலும் 1 ஆகச் சேமிக்கப்படுகிறது. நீங்கள் பார்க்கிறபடி, இத்தகைய திசையற்ற வரைபடங்களுக்கு அணிவரிசை மூலைவிட்டமாக சமச்சீராக மாறுகிறது.

இன்னும் குறிப்பாகப் பார்ப்போம். மேலே உள்ள அருகாமை அணிவரிசையில், ‘ஆப்பிள்’ முனைப்புள்ளி 0வது குறியீட்டிலும், ‘தோசை’ முனைப்புள்ளி 3வது குறியீட்டிலும் உள்ளது. எனவே, ‘ஆப்பிள்’ மற்றும் ‘தோசை’ ஆகியவற்றுக்கு இடையேயான விளிம்பு, (0,3) மற்றும் (3,0) ஆகிய நிலைகளில் 1 என்ற மதிப்பாகச் சேமிக்கப்படுகிறது, ஏனெனில் அந்த விளிம்பு இரு திசைகளிலும் செல்கிறது.

Example:

vertexFoodData = [‘Apple’, ‘Bread’, ‘Coffee’, ‘Dosa’]

adjacency_matrix = [

[0, 1, 1, 1],  # Edges for A

[1, 0, 1, 0],  # Edges for B

[1, 1, 0, 0],  # Edges for C

[1, 0, 0, 0]   # Edges for D

]

def print_adjacency_matrix(matrix):

print(“Adjacency Matrix:”)

for row in matrix:

print(row)

def print_connections(matrix, vertices):

print(“\nConnections for each vertex:”)

for i in range(len(vertices)):

print(f”{vertices[i]}: “, end=””)

for j in range(len(vertices)):

if matrix[i][j]:  # if there is a connection

print(vertices[j], end=” “)

print()  # new line

print(‘vertexFoodData:’,vertexFoodData)

print()

print_adjacency_matrix(adjacency_matrix)

print_connections(adjacency_matrix, vertexData)

Output:

vertexFoodData: [‘Apple’, ‘Bread’, ‘Coffee’, ‘Dosa’]

Adjacency Matrix:

[0, 1, 1, 1]

[1, 0, 1, 0]

[1, 1, 0, 0]

[1, 0, 0, 0]

Connections for each vertex:

Apple: Bread Coffee Dosa

Bread: Apple Coffee

Coffee: Apple Bread

Dosa: Apple

Using Classes

A more proper way to store a Graph is to add an abstraction layer using classes so that a Graph’s vertices, edges, and relevant methods, like algorithms that we will implement later, are contained in one place.

Programming languages with built-in object-oriented functionality like Python and Java, make implementation of Graphs using classes much easier than languages like C, without this built-in functionality.

கிளாஸ்களைப் பயன்படுத்தி

ஒரு வரைபடத்தைச் சேமிப்பதற்கான மிகவும் பொருத்தமான வழி, கிளாஸ்களைப் பயன்படுத்தி ஒரு சுருக்க அடுக்கைச் சேர்ப்பதாகும். இதன் மூலம், ஒரு வரைபடத்தின் முனைகள், விளிம்புகள் மற்றும் நாம் பின்னர் செயல்படுத்தவிருக்கும் வழிமுறைகள் போன்ற தொடர்புடைய முறைகள் அனைத்தும் ஒரே இடத்தில் அடங்கியிருக்கும்.

பைதான் மற்றும் ஜாவா போன்ற உள்ளமைக்கப்பட்ட பொருள் சார்ந்த செயல்பாடுகளைக் கொண்ட நிரலாக்க மொழிகள், இந்த உள்ளமைக்கப்பட்ட செயல்பாடு இல்லாத C போன்ற மொழிகளை விட, கிளாஸ்களைப் பயன்படுத்தி வரைபடங்களைச் செயல்படுத்துவதை மிகவும் எளிதாக்குகின்றன.

Example:

class Graph:

def init(self, size):

self.adj_matrix = [[0] * size for _ in range(size)]

self.size = size

self.vertex_fooddata = [”] * size

def add_edge(self, u, v):

if 0 <= u < self.size and 0 <= v < self.size:

self.adj_matrix[u][v] = 1

self.adj_matrix[v][u] = 1

def add_vertex_fooddata(self, vertex, data):

if 0 <= vertex < self.size:

self.vertex_fooddata[vertex] = data

def print_graph(self):

print(“Adjacency Matrix:”)

for row in self.adj_matrix:

print(‘ ‘.join(map(str, row)))

print(“\nVertex Food Data:”)

for vertex, data in enumerate(self.vertex_fooddata):

print(f”Vertex {vertex}: {data}”)

g = Graph(4)

g.add_vertex_fooddata(0, ‘Apple’)

g.add_vertex_fooddata(1, ‘Bread’)

g.add_vertex_fooddata(2, ‘Coffee’)

g.add_vertex_fooddata(3, ‘Dosa’)

g.add_edge(0, 1)  # Apple – Bread

g.add_edge(0, 2)  # Apple – Coffee

g.add_edge(0, 3)  # Apple – Dosa

g.add_edge(1, 2)  # Bread – Coffee

g.print_graph()

Output:

Adjacency Matrix:

0 1 1 1

1 0 1 0

1 1 0 0

1 0 0 0

Vertex Food Data:

Vertex 0: Apple

Vertex 1: Bread

Vertex 2: Coffee

Vertex 3: Dosa

Directed and Weighted Graphs

To implement a Graph that is directed and weighted, we just need to do a few changes to previous implementation of the undirected Graph.

To create directed Graphs, we just need to remove line 10 in the previous example code, so that the matrix is not automatically symmetric anymore.

The second change we need to do is to add a weight argument to the add_edge() method, so that instead of just having value 1 to indicate that there is an edge between two vertices, we use the actual weight value to define the edge.

திசை மற்றும் எடை கொண்ட ஒரு வரைபடத்தை (Graph) செயல்படுத்த, திசையற்ற வரைபடத்தின் முந்தைய செயலாக்கத்தில் சில மாற்றங்களைச் செய்தாலே போதும்.

திசை வரைபடங்களை உருவாக்க, முந்தைய எடுத்துக்காட்டுக் குறியீட்டில் உள்ள 10வது வரியை அகற்றினால் போதும், அதனால் அணி இனி தானாகவே சமச்சீராக இருக்காது.

நாம் செய்ய வேண்டிய இரண்டாவது மாற்றம், add_edge() முறைக்கு ஒரு எடை (weight) அளவுருவைச் சேர்ப்பது ஆகும். இதன் மூலம், இரண்டு முனைகளுக்கு இடையே ஒரு விளிம்பு இருப்பதைக் குறிக்க வெறும் மதிப்பு 1-ஐப் பயன்படுத்துவதற்குப் பதிலாக, விளிம்பை வரையறுக்க உண்மையான எடை மதிப்பைப் பயன்படுத்தலாம்.

Example:

class Graph:

def init(self, size):

self.adj_matrix = [[None] * size for _ in range(size)]

self.size = size

self.vertex_fooddata = [”] * size

def add_edge(self, u, v, weight):

if 0 <= u < self.size and 0 <= v < self.size:

self.adj_matrix[u][v] = weight

def add_vertex_fooddata(self, vertex, data):

if 0 <= vertex < self.size:

self.vertex_fooddata[vertex] = data

def print_graph(self):

print(“Adjacency Matrix:”)

for row in self.adj_matrix:

print(‘ ‘.join(map(lambda x: str(x) if x is not None else ‘0’, row)))

print(“\nVertex Food Data:”)

for vertex, data in enumerate(self.vertex_fooddata):

print(f”Vertex {vertex}: {data}”)

g = Graph(4)

g.add_vertex_fooddata(0, ‘Apple’)

g.add_vertex_fooddata(1, ‘Bread’)

g.add_vertex_fooddata(2, ‘Coffee’)

g.add_vertex_fooddata(3, ‘Dosa’)

g.add_edge(0, 1, 3)  # Apple -> Bread with weight 3

g.add_edge(0, 2, 2)  # Apple -> Coffee with weight 2

g.add_edge(3, 0, 4)  # Dosa -> Apple with weight 4

g.add_edge(2, 1, 1)  # Coffee -> Bread with weight 1

g.print_graph()

Output:

Adjacency Matrix:

0 3 2 0

0 0 0 0

0 1 0 0

4 0 0 0

Vertex Food Data:

Vertex 0: Apple

Vertex 1: Bread

Vertex 2: Coffee

Vertex 3: Dosa

Graphs Traversal

To traverse a Graph means to start in one vertex, and go along the edges to visit other vertices until all vertices, or as many as possible, have been visited.

வரைபடங்களின் ஊடுருவல்

ஒரு வரைபடத்தை ஊடுருவுதல் என்பது, ஒரு முனையில் தொடங்கி, விளிம்புகள் வழியாகச் சென்று, அனைத்து முனைகளும் அல்லது முடிந்தவரை பல முனைகளும் பார்வையிடப்படும் வரை மற்ற முனைகளைப் பார்வையிடுவதாகும்.

The two most common ways a Graph can be traversed are:

• Depth First Search (DFS)
• Breadth First Search (BFS)

DFS is usually implemented using a Stack or by the use of recursion (which utilizes the call stack), while BFS is usually implemented using a Queue.

ஒரு வரைபடத்தை கடந்து செல்வதற்கான இரண்டு பொதுவான வழிகள்:

• ஆழம் முதல் தேடல் (DFS)
• அகலம் முதல் தேடல் (BFS)

DFS பொதுவாக ஒரு ஸ்டேக்கைப் பயன்படுத்தியோ அல்லது மீள்சுழற்சியைப் பயன்படுத்தியோ (இது கால் ஸ்டேக்கைப் பயன்படுத்துகிறது) செயல்படுத்தப்படுகிறது, அதே சமயம் BFS பொதுவாக ஒரு கியூவைப் பயன்படுத்தி செயல்படுத்தப்படுகிறது.

Depth First Search Traversal

Depth First Search is said to go “deep” because it visits a vertex, then an adjacent vertex, and then that vertex’ adjacent vertex, and so on, and in this way the distance from the starting vertex increases for each recursive iteration.

Example

class Graph:

def init(self, size):

self.adj_matrix = [[0] * size for _ in range(size)]

self.size = size

self.vertex_fooddata = [”] * size

def add_edge(self, u, v):

if 0 <= u < self.size and 0 <= v < self.size:

self.adj_matrix[u][v] = 1

self.adj_matrix[v][u] = 1

def add_vertex_fooddata(self, vertex, data):

if 0 <= vertex < self.size:

self.vertex_fooddata[vertex] = data

def print_graph(self):

print(“Adjacency Matrix:”)

for row in self.adj_matrix:

print(‘ ‘.join(map(str, row)))

print(“\nVertex Food Data:”)

for vertex, data in enumerate(self.vertex_fooddata):

print(f”Vertex {vertex}: {data}”)

def dfs_util(self, v, visited):

visited[v] = True

print(self.vertex_fooddata[v], end=’ ‘)

for i in range(self.size):

if self.adj_matrix[v][i] == 1 and not visited[i]:

self.dfs_util(i, visited)

def dfs(self, start_vertex_fooddata):

visited = [False] * self.size

start_vertex = self.vertex_fooddata.index(start_vertex_fooddata)

self.dfs_util(start_vertex, visited)

g = Graph(7)

g.add_vertex_fooddata(0, ‘Apple’)

g.add_vertex_fooddata(1, ‘Bread’)

g.add_vertex_fooddata(2, ‘Coffee’)

g.add_vertex_fooddata(3, ‘Dosa’)

g.add_vertex_fooddata(4, ‘Egg’)

g.add_vertex_fooddata(5, ‘Fish’)

g.add_vertex_fooddata(6, ‘Grape’)

g.add_edge(3, 0)  # Dosa – Apple

g.add_edge(0, 2)  # Apple – Coffee

g.add_edge(0, 3)  # Apple – Dosa

g.add_edge(0, 4)  # Apple – Egg

g.add_edge(4, 2)  # Egg – Coffee

g.add_edge(2, 5)  # Coffee – Fish

g.add_edge(2, 1)  # Coffee – Bread

g.add_edge(2, 6)  # Coffee – Grape

g.add_edge(1, 5)  # Bread – Fish

g.print_graph()

print(“\nDepth First Search starting from vertex Dosa:”)

g.dfs(‘Dosa’)

Output:

Adjacency Matrix:

0 0 1 1 1 0 0

0 0 1 0 0 1 0

1 1 0 0 1 1 1

1 0 0 0 0 0 0

1 0 1 0 0 0 0

0 1 1 0 0 0 0

0 0 1 0 0 0 0

Vertex Food Data:

Vertex 0: Apple

Vertex 1: Bread

Vertex 2: Coffee

Vertex 3: Dosa

Vertex 4: Egg

Vertex 5: Fish

Vertex 6: Grape

Depth First Search starting from vertex Dosa:

Dosa Apple Coffee Bread Fish Egg Grape

The DFS traversal starts when the dfs() method is called.

The visited array is first set to false for all vertices, because no vertices are visited yet at this point.

The visited array is sent as an argument to the dfs_util() method. When the visited array is sent as an argument like this, it is actually just a reference to the visited array that is sent to the dfs_util() method, and not the actual array with the values inside. So there is always just one visited array in our program, and the dfs_util() method can make changes to it as nodes are visited .

For the current vertex v, all adjacent nodes are called recursively if they are not already visited.

dfs() முறை அழைக்கப்படும்போது DFS பயணம் தொடங்குகிறது.

இந்தக் கட்டத்தில் எந்த முனைகளும் இன்னும் பார்வையிடப்படாததால், முதலில் அனைத்து முனைகளுக்கும் ‘visited’ அணிவரிசை ‘false’ என அமைக்கப்படுகிறது.

‘visited’ அணிவரிசை dfs_util() முறைக்கு ஒரு வாதமாக அனுப்பப்படுகிறது. ‘visited’ அணிவரிசை இந்த வழியில் ஒரு வாதமாக அனுப்பப்படும்போது, ​​அது உண்மையில் மதிப்புகளைக் கொண்ட உண்மையான அணிவரிசை அல்ல, மாறாக ‘visited’ அணிவரிசைக்கான ஒரு குறிப்பு மட்டுமே dfs_util() முறைக்கு அனுப்பப்படுகிறது. எனவே, நமது நிரலில் எப்போதும் ஒரே ஒரு ‘visited’ அணிவரிசை மட்டுமே இருக்கும், மேலும் முனைகள் பார்வையிடப்படும்போது dfs_util() முறையானது அதில் மாற்றங்களைச் செய்ய முடியும்.

தற்போதைய முனை v-க்கு, அருகிலுள்ள அனைத்து முனைகளும் ஏற்கனவே பார்வையிடப்படவில்லை என்றால், அவை மீள்சுழல் முறையில் அழைக்கப்படுகின்றன.

Breadth First Search Traversal

Breadth First Search visits all adjacent vertices of a vertex before visiting neighboring vertices to the adjacent vertices. This means that vertices with the same distance from the starting vertex are visited before vertices further away from the starting vertex are visited.

அகல முதல் தேடல் வழிமுறை

அகல முதல் தேடல் முறையில், ஒரு முனையின் அருகிலுள்ள முனைகளுக்குச் செல்லும் முன், அந்த முனையின் அனைத்து அண்டை முனைகளும் பார்வையிடப்படுகின்றன. இதன் பொருள், தொடக்க முனையிலிருந்து ஒரே தூரத்தில் உள்ள முனைகள், தொடக்க முனையிலிருந்து அதிக தூரத்தில் உள்ள முனைகளுக்குச் செல்வதற்கு முன்பு பார்வையிடப்படுகின்றன என்பதாகும்.

Example:

class Graph:

def init(self, size):

self.adj_matrix = [[0] * size for _ in range(size)]

self.size = size

self.vertex_fooddata = [”] * size

def add_edge(self, u, v):

if 0 <= u < self.size and 0 <= v < self.size:

self.adj_matrix[u][v] = 1

self.adj_matrix[v][u] = 1

def add_vertex_fooddata(self, vertex, data):

if 0 <= vertex < self.size:

self.vertex_fooddata[vertex] = data

def print_graph(self):

print(“Adjacency Matrix:”)

for row in self.adj_matrix:

print(‘ ‘.join(map(str, row)))

print(“\nVertex Data:”)

for vertex, data in enumerate(self.vertex_fooddata):

print(f”Vertex {vertex}: {data}”)

def bfs(self, start_vertex_fooddata):

queue = [self.vertex_fooddata.index(start_vertex_fooddata)]

visited = [False] * self.size

visited[queue[0]] = True

while queue:

current_vertex = queue.pop(0)

print(self.vertex_fooddata[current_vertex], end=’ ‘)

for i in range(self.size):

if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:

queue.append(i)

visited[i] = True

g = Graph(7)

g.add_vertex_fooddata(0, ‘Apple’)

g.add_vertex_fooddata(1, ‘Bread’)

g.add_vertex_fooddata(2, ‘Coffee’)

g.add_vertex_fooddata(3, ‘Dosa’)

g.add_vertex_fooddata(4, ‘Egg’)

g.add_vertex_fooddata(5, ‘Fish’)

g.add_vertex_fooddata(6, ‘Grape’)

g.add_edge(3, 0)  # Dosa – Apple

g.add_edge(0, 2)  # Apple – Coffee

g.add_edge(0, 3)  # Apple – Dosa

g.add_edge(0, 4)  # Apple – Egg

g.add_edge(4, 2)  # Egg – Coffee

g.add_edge(2, 5)  # Coffee – Fish

g.add_edge(2, 1)  # Coffee – Bread

g.add_edge(2, 6)  # Coffee – Grape

g.add_edge(1, 5)  # Bread – Fish

g.print_graph()

print(“\nBreadth First Search starting from vertex Dosa:”)

g.bfs(‘Dosa’)

Output:

Adjacency Matrix:

0 0 1 1 1 0 0

0 0 1 0 0 1 0

1 1 0 0 1 1 1

1 0 0 0 0 0 0

1 0 1 0 0 0 0

0 1 1 0 0 0 0

0 0 1 0 0 0 0

Vertex Data:

Vertex 0: Apple

Vertex 1: Bread

Vertex 2: Coffee

Vertex 3: Dosa

Vertex 4: Egg

Vertex 5: Fish

Vertex 6: Grape

Breadth First Search starting from vertex Dosa:

Dosa Apple Coffee Egg Bread Fish Grape

The bfs() method starts by creating a queue with the start vertex inside, creating a visited array, and setting the start vertex as visited.

The BFS traversal works by taking a vertex from the queue, printing it, and adding adjacent vertices to the queue if they are not visited yet, and then continue to take vertices from the queue in this way. The traversal finishes when the last element in the queue has no unvisited adjacent vertices.

bfs() முறைமையானது, தொடக்க முனையைக் கொண்ட ஒரு வரிசையை உருவாக்குவதன் மூலமும், ஒரு பார்வையிடப்பட்ட அணிவரிசையை உருவாக்குவதன் மூலமும், தொடக்க முனையைப் பார்வையிடப்பட்டதாகக் குறிப்பதன் மூலமும் தொடங்குகிறது.

BFS கடந்துசெல்லும் செயல்முறையானது, வரிசையிலிருந்து ஒரு முனையை எடுத்து, அதைப் பதிப்பித்து, இதுவரை பார்வையிடப்படாத அருகிலுள்ள முனைகளை வரிசையில் சேர்ப்பதன் மூலமும், பின்னர் இந்த வழியில் வரிசையிலிருந்து முனைகளைத் தொடர்ந்து எடுப்பதன் மூலமும் செயல்படுகிறது. வரிசையில் உள்ள கடைசி உறுப்புக்கு பார்வையிடப்படாத அருகிலுள்ள முனைகள் எதுவும் இல்லாதபோது இந்த கடந்துசெல்லும் செயல்முறை முடிவடைகிறது.

The AVL Tree is a type of Binary Search Tree named after two Soviet inventors Georgy Adelson-Velsky and Evgenii Landis who invented the AVL Tree in 1962.

AVL trees are self-balancing, which means that the tree height is kept to a minimum so that a very fast runtime is guaranteed for searching, inserting and deleting nodes, with time complexity O(logn)

ஏவிஎல் மரம் என்பது ஒரு வகை இருமத் தேடல் மரம் ஆகும். இது 1962-ல் ஏவிஎல் மரத்தைக் கண்டுபிடித்த ஜார்ஜி அடெல்சன்-வெல்ஸ்கி மற்றும் எவ்ஜெனி லாண்டிஸ் ஆகிய இரண்டு சோவியத் கண்டுபிடிப்பாளர்களின் பெயரால் அழைக்கப்படுகிறது.

ஏவிஎல் மரங்கள் சுய-சமநிலைப்படுத்தும் தன்மை கொண்டவை. இதன் பொருள், மரத்தின் உயரம் குறைந்தபட்ச அளவில் பராமரிக்கப்படுவதால், முனைகளைத் தேடுதல், செருகுதல் மற்றும் நீக்குதல் போன்ற செயல்பாடுகளுக்கு மிக வேகமான இயக்க நேரம் உறுதி செய்யப்படுகிறது. இதன் நேரச் சிக்கல்தன்மை O(log n) ஆகும்.

The only difference between a regular Binary Search Tree and an AVL Tree is that AVL Trees do rotation operations in addition, to keep the tree balance.

A Binary Search Tree is in balance when the difference in height between left and right subtrees is less than 2.

By keeping balance, the AVL Tree ensures a minimum tree height, which means that search, insert, and delete operations can be done really fast.

ஒரு சாதாரண பைனரி தேடல் மரம் மற்றும் ஒரு ஏவிஎல் மரத்திற்கு இடையேயான ஒரே வித்தியாசம் என்னவென்றால், ஏவிஎல் மரங்கள் மரத்தின் சமநிலையைப் பராமரிப்பதற்காகக் கூடுதலாகச் சுழற்சிச் செயல்பாடுகளைச் செய்கின்றன.

ஒரு பைனரி தேடல் மரத்தின் இடது மற்றும் வலது துணை மரங்களுக்கு இடையேயான உயர வேறுபாடு 2-ஐ விடக் குறைவாக இருக்கும்போது, ​​அந்த மரம் சமநிலையில் இருப்பதாகக் கூறப்படுகிறது.

சமநிலையைப் பராமரிப்பதன் மூலம், ஏவிஎல் மரம் ஒரு குறைந்தபட்ச மர உயரத்தை உறுதி செய்கிறது. இதன் காரணமாக, தேடல், செருகுதல் மற்றும் நீக்குதல் போன்ற செயல்பாடுகளை மிக வேகமாகச் செய்ய முடியும்.

The two trees above are both Binary Search Trees, they have the same nodes, and the same in-order traversal (alphabetical), but the height is very different because the AVL Tree has balanced itself.

மேலே உள்ள இரண்டு மரங்களும் இருமத் தேடல் மரங்கள் ஆகும்; அவை ஒரே முனைகளைக் கொண்டுள்ளன, மேலும் அவற்றின் இன்-ஆர்டர் வரிசைப்படுத்தலும் (அகர வரிசைப்படி) ஒரே மாதிரியாக உள்ளது, ஆனால் ஏவிஎல் மரம் தன்னைத்தானே சமநிலைப்படுத்திக் கொண்டதால், அவற்றின் உயரம் மிகவும் வேறுபடுகிறது.

Left and Right Rotations

To restore balance in an AVL Tree, left or right rotations are done, or a combination of left and right rotations.

இடது மற்றும் வலது சுழற்சிகள்

ஒரு AVL மரத்தில் சமநிலையை மீட்டெடுக்க, இடது அல்லது வலது சுழற்சிகள் செய்யப்படுகின்றன, அல்லது இடது மற்றும் வலது சுழற்சிகளின் கலவை செய்யப்படுகிறது.

The Balance Factor

A node’s balance factor is the difference in subtree heights.

The subtree heights are stored at each node for all nodes in an AVL Tree, and the balance factor is calculated based on its subtree heights to check if the tree has become out of balance.

The height of a subtree is the number of edges between the root node of the subtree and the leaf node farthest down in that subtree.

சமநிலை காரணி

ஒரு முனையின் சமநிலை காரணி என்பது அதன் துணை மரங்களின் உயரங்களுக்கு இடையிலான வேறுபாடு ஆகும்.

ஒரு AVL மரத்தில் உள்ள அனைத்து முனைகளுக்கும், துணை மரங்களின் உயரங்கள் ஒவ்வொரு முனையிலும் சேமிக்கப்படுகின்றன, மேலும் மரம் சமநிலையற்றதாகிவிட்டதா என்பதைச் சரிபார்க்க, அதன் துணை மரங்களின் உயரங்களின் அடிப்படையில் சமநிலை காரணி கணக்கிடப்படுகிறது.

ஒரு துணை மரத்தின் உயரம் என்பது, அந்த துணை மரத்தின் மூல முனைக்கும், அந்த துணை மரத்தில் மிகக் கீழே உள்ள இலை முனைக்கும் இடையே உள்ள விளிம்புகளின் எண்ணிக்கை ஆகும்.

The Balance Factor (BF)

The Balance Factor (BF) for a node (X) is the difference in height between its right and left subtrees.

BF(X) = height(rightSubtree(X)) – height(leftSubtree(X))

Balance factor values

• 0: The node is in balance.
• more than 0: The node is “right heavy”.
• less than 0: The node is “left heavy”.

If the balance factor is less than -1, or more than 1, for one or more nodes in the tree, the tree is considered not in balance, and a rotation operation is needed to restore balance.

சமநிலை காரணி  (BF)

ஒரு முனையின் (X) சமநிலை காரணி (BF) என்பது அதன் வலது மற்றும் இடது துணை மரங்களின் உயரங்களுக்கு இடையிலான வேறுபாடு ஆகும்.

BF(X) = உயரம்(வலது துணைமரம்(X)) – உயரம்(இடது துணைமரம்(X))

சமநிலை காரணி மதிப்புகள்:

• 0: முனை சமநிலையில் உள்ளது.
• 0-ஐ விட அதிகம்: முனை “வலதுபுறம் கனமாக” உள்ளது.
• 0-ஐ விடக் குறைவு: முனை “இடதுபுறம் கனமாக” உள்ளது.

மரத்திலுள்ள ஒன்று அல்லது அதற்கு மேற்பட்ட முனைகளுக்கு சமநிலை காரணி -1-ஐ விடக் குறைவாகவோ அல்லது 1-ஐ விட அதிகமாகவோ இருந்தால், அந்த மரம் சமநிலையில் இல்லை என்று கருதப்படுகிறது, மேலும் சமநிலையை மீட்டெடுக்க ஒரு சுழற்சி செயல்பாடு தேவைப்படுகிறது.

The Four “out-of-balance” Cases

When the balance factor of just one node is less than -1, or more than 1, the tree is regarded as out of balance, and a rotation is needed to restore balance.

There are four different ways an AVL Tree can be out of balance, and each of these cases require a different rotation operation.

சமநிலையற்ற நான்கு நிலைகள்

ஏதேனும் ஒரு முனையின் சமநிலை காரணி -1-ஐ விடக் குறைவாகவோ அல்லது 1-ஐ விட அதிகமாகவோ இருந்தால், அந்த மரம் சமநிலையற்றதாகக் கருதப்படுகிறது, மேலும் சமநிலையை மீட்டெடுக்க ஒரு சுழற்சி தேவைப்படுகிறது.

ஒரு AVL மரம் சமநிலையற்று இருக்க நான்கு வெவ்வேறு வழிகள் உள்ளன, மேலும் இந்த ஒவ்வொரு நிலைக்கும் ஒரு வெவ்வேறு சுழற்சி செயல்பாடு தேவைப்படுகிறது.

Left-Left (LL)

The unbalanced node and its left child node are both left-heavy.

Rotation to Restore Balance : A single right rotation.

இடம்-இடம் (LL)

சமநிலையற்ற முனையும் அதன் இடது குழந்தை முனையும் இரண்டும் இடதுபுறம் கனமாக உள்ளன. சமநிலையை மீட்டெடுப்பதற்கான சுழற்சி: ஒரு ஒற்றை வலதுபுறச் சுழற்சி.

Example:

Add Bis will look unbalanced as shown below

கீழே காட்டப்பட்டுள்ளபடி Bis ஐச் சேர்ப்பது சமநிலையற்றதாகத் தோன்றும்.

Single right rotation /ஒற்றை வலது சுழற்சி

Right-Right (RR)

The unbalanced node and its right child node are both right-heavy.

Rotation to Restore Balance :A single left rotation.

வலது-வலது (RR)

சமநிலையற்ற முனையும் அதன் வலது குழந்தை முனையும் இரண்டும் வலதுபுறம் கனமாக உள்ளன.

சமநிலையை மீட்டெடுப்பதற்கான சுழற்சி: ஒரு ஒற்றை இடதுபுறச் சுழற்சி.

Example:

Insert Idly on above tree, right side is heavy /மேலே உள்ள மரத்தில் இட்லியைச் செருகவும், வலது பக்கம் கனமாக உள்ளது.

Single left rotation make AVL tree balanced / ஒற்றை இடது சுழற்சி ஏவிஎல் மரத்தை சமநிலைப்படுத்துகிறது.

Left-Right (LR)

The unbalanced node is left heavy, and its left child node is right heavy.

Rotation to Restore Balance : First do a left rotation on the left child node, then do a right rotation on the unbalanced node.

இடம்-வலம் (LR)

சமநிலையற்ற முனை இடதுபுறம் கனமாக உள்ளது, மேலும் அதன் இடது குழந்தை முனை வலதுபுறம் கனமாக உள்ளது.

சமநிலையை மீட்டெடுப்பதற்கான சுழற்சி: முதலில் இடது குழந்தை முனையில் ஒரு இடதுபுறச் சுழற்சியைச் செய்யவும், பின்னர் சமநிலையற்ற முனையில் ஒரு வலதுபுறச் சுழற்சியைச் செய்யவும்.

Example:

Insert Dosa to above AVL Tree which is unbalanced  /சமநிலையற்ற நிலையில் உள்ள மேற்கண்ட AVL மரத்தில் ‘தோசை’ என்ற சொல்லைச் செருகவும்.

In this LR case, a left rotation is first done on the left child node, and then a right rotation is done on the original unbalanced node.

இந்த LR நிலையில், முதலில் இடது குழந்தைப் புள்ளி மீது ஒரு இடது சுழற்சியும், பின்னர் அசல் சமநிலையற்ற புள்ளி மீது ஒரு வலது சுழற்சியும் செய்யப்படுகிறது.

The Right-Left (RL) Case

The Right-Left case is when the unbalanced node is right heavy, and its right child node is left heavy.

In this case we first do a right rotation on the unbalanced node’s right child, and then we do a left rotation on the unbalanced node itself.

வலது-இடது (RL) நிலை

வலது-இடது நிலை என்பது, சமநிலையற்ற முனை வலதுபுறம் கனமாக இருப்பதும், அதன் வலது குழந்தை முனை இடதுபுறம் கனமாக இருப்பதும் ஆகும்.

இந்த நிலையில், நாம் முதலில் சமநிலையற்ற முனையின் வலது குழந்தை முனையில் ஒரு வலது சுழற்சியைச் செய்கிறோம், பின்னர் சமநிலையற்ற முனையிலேயே ஒரு இடது சுழற்சியைச் செய்கிறோம்.

After inserting node Egg, we get a Right-Left case because node Dosa becomes unbalanced and right heavy, and its right child is left heavy. (First image) To restore balance, a right rotation is first done on node Grap, and then a left rotation is done on node Dosa.

எக் (Egg) நோடைச் செருகிய பிறகு, நோட் டோசா சமநிலையற்றதாகவும், வலதுபுறம் கனமாகவும் மாறுவதாலும், அதன் வலதுபுறச் சைல்டு இடதுபுறம் கனமாக இருப்பதாலும், நமக்கு ஒரு வலது-இடது நிலை ஏற்படுகிறது. (முதல் படம்) சமநிலையை மீட்டெடுக்க, முதலில் கிராப் (Grap) நோடில் ஒரு வலது சுழற்சியும், பின்னர் டோசா (Dosa) நோடில் ஒரு இடது சுழற்சியும் செய்யப்படுகிறது.

Retracing in AVL Trees

After inserting or deleting a node in an AVL tree, the tree may become unbalanced. To find out if the tree is unbalanced, we need to update the heights and recalculate the balance factors of all ancestor nodes.

This process, known as retracing, is handled through recursion. As the recursive calls propagate back to the root after an insertion or deletion, each ancestor node’s height is updated and the balance factor is recalculated. If any ancestor node is found to have a balance factor outside the range of -1 to 1, a rotation is performed at that node to restore the tree’s balance.

AVL மரங்களில் பின்னோக்கிச் செல்லுதல்

ஒரு AVL மரத்தில் ஒரு முனையைச் செருகிய அல்லது நீக்கிய பிறகு, அந்த மரம் சமநிலையற்றதாக மாறக்கூடும். மரம் சமநிலையற்றதாக உள்ளதா என்பதைக் கண்டறிய, நாம் அனைத்து மூதாதை முனைகளின் உயரங்களையும் புதுப்பித்து, சமநிலை காரணிகளை மீண்டும் கணக்கிட வேண்டும்.

பின்னோக்கிச் செல்லுதல் என்று அழைக்கப்படும் இந்தச் செயல்முறை, மீள்சுழற்சி மூலம் கையாளப்படுகிறது. ஒரு செருகல் அல்லது நீக்கத்திற்குப் பிறகு மீள்சுழற்சி அழைப்புகள் வேர் முனைக்குத் திரும்பும்போது, ​​ஒவ்வொரு மூதாதை முனையின் உயரமும் புதுப்பிக்கப்பட்டு, சமநிலை காரணி மீண்டும் கணக்கிடப்படுகிறது. ஏதேனும் ஒரு மூதாதை முனையின் சமநிலை காரணி -1 முதல் 1 வரையிலான வரம்பிற்கு வெளியே இருப்பது கண்டறியப்பட்டால், மரத்தின் சமநிலையை மீட்டெடுக்க அந்த முனையில் ஒரு சுழற்சி செய்யப்படுகிறது.

After inserting node Fish, the nodes Coff, Egg and Horl are all unbalanced, but since retracing works through recursion, the unbalance at node Horl is discovered and fixed first, which in this case also fixes the unbalance in nodes Egg and Coff

Fishமுனையைச் செருகிய பிறகு, Coff, Egg மற்றும் Horl முனைகள் அனைத்தும் சமநிலையற்றவை, ஆனால் மறுபரிசீலனை மறுநிகழ்வு மூலம் செயல்படுவதால், முனை Horl உள்ள சமநிலையின்மை முதலில் கண்டறியப்பட்டு சரி செய்யப்படுகிறது, இது இந்த விஷயத்தில் முட்டை மற்றும் Coff முனைகளிலும் உள்ள சமநிலையின்மையை சரிசெய்கிறது.

After node Fish is inserted, the code will retrace, calculating balancing factors as it propagates back up towards the root node. When node Horl reached and the balancing factor -2 is calculated, a right rotation is done. Only after this rotation is done, the code will continue to retrace, calculating balancing factors further up on ancestor nodes Egg and Coff.

Because of the rotation, balancing factors for nodes Egg and Coff stay the same as before node Fish was inserted.

Fish முனைமம் செருகப்பட்ட பிறகு, குறியீடு மீண்டும் பின்னோக்கிச் சென்று, மூல முனைமத்தை நோக்கி மேலே பரவும்போது சமநிலைப்படுத்தும் காரணிகளைக் கணக்கிடும். Horl முனைமத்தை அடைந்து, சமநிலைப்படுத்தும் காரணி -2 எனக் கணக்கிடப்பட்டதும், ஒரு வலதுபுறச் சுழற்சி செய்யப்படுகிறது. இந்தச் சுழற்சி செய்யப்பட்ட பின்னரே, குறியீடு மீண்டும் பின்னோக்கிச் சென்று, அதன் மூதாதை முனைமங்களான Egg மற்றும் Coff ஆகியவற்றில் உள்ள சமநிலைப்படுத்தும் காரணிகளைக் கணக்கிடும்.

Insert Node

The implementation below builds an AVL tree based on a list of food items, to create the AVL Tree in the simulation above. The last node to be inserted ‘Fish’, also triggers a right rotation, just like in the simulation above.

முனையைச் செருகுதல்

கீழே உள்ள செயலாக்கம், மேலே உள்ள உருவகப்படுத்துதலில் AVL மரத்தை உருவாக்குவதற்காக, உணவுப் பொருட்களின் பட்டியலின் அடிப்படையில் ஒரு AVL மரத்தை உருவாக்குகிறது. செருகப்பட வேண்டிய கடைசி முனையான ‘மீன்’, மேலே உள்ள உருவகப்படுத்துதலில் உள்ளதைப் போலவே, ஒரு வலதுபுறச் சுழற்சியைத் தூண்டுகிறது.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

self.height = 1

def getHeight(node):

if not node:

return 0

return node.height

def getBalance(node):

if not node:

return 0

return getHeight(node.left) – getHeight(node.right)

def rightRotate(y):

print(‘Rotate right on node’,y.data)

x = y.left

T2 = x.right

x.right = y

y.left = T2

y.height = 1 + max(getHeight(y.left), getHeight(y.right))

x.height = 1 + max(getHeight(x.left), getHeight(x.right))

return x

def leftRotate(x):

print(‘Rotate left on node’,x.data)

y = x.right

T2 = y.left

y.left = x

x.right = T2

x.height = 1 + max(getHeight(x.left), getHeight(x.right))

y.height = 1 + max(getHeight(y.left), getHeight(y.right))

return y

def insert(node, data):

if not node:

return TreeNode(data)

if data < node.data:

node.left = insert(node.left, data)

elif data > node.data:

node.right = insert(node.right, data)

Update the balance factor and balance the tree

node.height = 1 + max(getHeight(node.left), getHeight(node.right))

balance = getBalance(node)

Balancing the tree

Left Left

if balance > 1 and getBalance(node.left) >= 0:

return rightRotate(node)

Left Right

if balance > 1 and getBalance(node.left) < 0:

node.left = leftRotate(node.left)

return rightRotate(node)

Right Right

if balance < -1 and getBalance(node.right) <= 0:

return leftRotate(node)

Right Left

if balance < -1 and getBalance(node.right) > 0:

node.right = rightRotate(node.right)

return leftRotate(node)

return node

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

Inserting nodes

root = None

letters = [‘Coff’, ‘Brew’, ‘Egg’, ‘Appl’, ‘Dosa’, ‘Horl’, ‘Grap’, ‘Fish’]

for letter in letters:

root = insert(root, letter)

inOrderTraversal(root)

Output:

Rotate right on node Horl

Appl, Brew, Coff, Dosa, Egg, Fish, Grap, Horl

Delete Node

To delete a node in an AVL Tree, the same code to restore balance is needed as for the code to insert a node.

முனையை நீக்கு

AVL மரத்தில் ஒரு முனையை நீக்க, சமநிலையை மீட்டெடுக்க ஒரு முனையைச் செருகுவதற்கான குறியீட்டிற்குத் தேவைப்படும் அதே குறியீடு தேவை.

Example

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

self.height = 1

def getHeight(node):

if not node:

return 0

return node.height

def getBalance(node):

if not node:

return 0

return getHeight(node.left) – getHeight(node.right)

def rightRotate(y):

x = y.left

T2 = x.right

x.right = y

y.left = T2

y.height = 1 + max(getHeight(y.left), getHeight(y.right))

x.height = 1 + max(getHeight(x.left), getHeight(x.right))

return x

def leftRotate(x):

y = x.right

T2 = y.left

y.left = x

x.right = T2

x.height = 1 + max(getHeight(x.left), getHeight(x.right))

y.height = 1 + max(getHeight(y.left), getHeight(y.right))

return y

def insert(node, data):

if not node:

return TreeNode(data)

if data < node.data:

node.left = insert(node.left, data)

elif data > node.data:

node.right = insert(node.right, data)

Update the balance factor and balance the tree

node.height = 1 + max(getHeight(node.left), getHeight(node.right))

balance = getBalance(node)

Balancing the tree

Left Left

if balance > 1 and getBalance(node.left) >= 0:

return rightRotate(node)

Left Right

if balance > 1 and getBalance(node.left) < 0:

node.left = leftRotate(node.left)

return rightRotate(node)

Right Right

if balance < -1 and getBalance(node.right) <= 0:

return leftRotate(node)

Right Left

if balance < -1 and getBalance(node.right) > 0:

node.right = rightRotate(node.right)

return leftRotate(node)

return node

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

def minValueNode(node):

current = node

while current.left is not None:

current = current.left

return current

def minValueNode(node):

current = node

while current.left is not None:

current = current.left

return current

def delete(node, data):

if not node:

return node

if data < node.data:

node.left = delete(node.left, data)

elif data > node.data:

node.right = delete(node.right, data)

else:

if node.left is None:

temp = node.right

node = None

return temp

elif node.right is None:

temp = node.left

node = None

return temp

temp = minValueNode(node.right)

node.data = temp.data

node.right = delete(node.right, temp.data)

if node is None:

return node

Update the balance factor and balance the tree

node.height = 1 + max(getHeight(node.left), getHeight(node.right))

balance = getBalance(node)

Balancing the tree

Left Left

if balance > 1 and getBalance(node.left) >= 0:

return rightRotate(node)

Left Right

if balance > 1 and getBalance(node.left) < 0:

node.left = leftRotate(node.left)

return rightRotate(node)

Right Right

if balance < -1 and getBalance(node.right) <= 0:

return leftRotate(node)

Right Left

if balance < -1 and getBalance(node.right) > 0:

node.right = rightRotate(node.right)

return leftRotate(node)

return node

Inserting the food items

root = None

foods = [‘Coff’, ‘Brew’, ‘Egg’, ‘Appl’, ‘Dosa’, ‘Horl’, ‘Grap’, ‘Fish’]

for food in foods:

root = insert(root, food)

inOrderTraversal(root)

print(‘\nDeleting Appl’)

root = delete(root,’Appl’)

inOrderTraversal(root)

Output:

Appl, Brew, Coff, Dosa, Egg, Fish, Grap, Horl,

Deleting Appl

Brew, Coff, Dosa, Egg, Fish, Grap, Horl,

A Binary Search Tree is a Binary Tree where every node’s left child has a lower value, and every node’s right child has a higher value.

A clear advantage with Binary Search Trees is that operations like search, delete, and insert are fast and done without having to shift values in memory.

ஒரு இருமத் தேடல் மரம் என்பது ஒரு இரும மரம் ஆகும். இதில் ஒவ்வொரு முனையின் இடது குழந்தையும் குறைந்த மதிப்பையும், வலது குழந்தையும் அதிக மதிப்பையும் கொண்டிருக்கும்.

இருமத் தேடல் மரங்களின் ஒரு தெளிவான நன்மை என்னவென்றால், தேடுதல், நீக்குதல் மற்றும் செருகுதல் போன்ற செயல்பாடுகள் வேகமாகவும், நினைவகத்தில் மதிப்புகளை நகர்த்த வேண்டிய அவசியம் இல்லாமலும் செய்யப்படுகின்றன.

Binary Search Tree (BST) is a type of Binary Tree data structure, where the following properties must be true for any node “X” in the tree:

• The X node’s left child and all of its descendants (children, children’s children, and so on) have lower values than X’s value.
• The right child, and all its descendants have higher values than X’s value.
• Left and right subtrees must also be Binary Search Trees.

These properties makes it faster to search, add and delete values than a regular binary tree.

To make this as easy to understand and implement as possible, let’s also assume that all values in a Binary Search Tree are unique.

இருமத் தேடல் மரம் (BST) என்பது ஒரு வகை இரும மரத் தரவுக் கட்டமைப்பாகும். இதில், மரத்தில் உள்ள எந்தவொரு ‘X’ முனைகளுக்கும் பின்வரும் பண்புகள் உண்மையாக இருக்க வேண்டும்:

• ‘X’ முனையின் இடது குழந்தை மற்றும் அதன் அனைத்து வழித்தோன்றல்களும் (குழந்தைகள், குழந்தைகளின் குழந்தைகள் மற்றும் பல) ‘X’-இன் மதிப்பை விடக் குறைந்த மதிப்புகளைக் கொண்டிருக்கும்.
• வலது குழந்தை மற்றும் அதன் அனைத்து வழித்தோன்றல்களும் ‘X’-இன் மதிப்பை விட அதிக மதிப்புகளைக் கொண்டிருக்கும்.
• இடது மற்றும் வலது துணை மரங்களும் பைனரி தேடல் மரங்களாகவே இருக்க வேண்டும்.

இந்த பண்புகள், ஒரு சாதாரண பைனரி மரத்தை விட மதிப்புகளைத் தேடுவது, சேர்ப்பது மற்றும் நீக்குவதை வேகமாக்குகின்றன.

இதை முடிந்தவரை எளிதாகப் புரிந்துகொள்வதற்கும் செயல்படுத்துவதற்கும், ஒரு இருமத் தேடல் மரத்தில் உள்ள அனைத்து மதிப்புகளும் தனித்துவமானவை என்றும் நாம் கருதுவோம்.

The size of a tree is the number of nodes in it (n).

A subtree starts with one of the nodes in the tree as a local root, and consists of that node and all its descendants.

The descendants of a node are all the child nodes of that node, and all their child nodes, and so on. Just start with a node, and the descendants will be all nodes that are connected below that node.

The node’s height is the maximum number of edges between that node and a leaf node.

A node’s in-order successor is the node that comes after it if we were to do in-order traversal. In-order traversal of the BST above would result in node 13 coming before node 14, and so the successor of node 13 is node 14.

ஒரு மரத்தின் அளவு என்பது அதில் உள்ள முனைகளின் எண்ணிக்கை (n) ஆகும்.

ஒரு துணை மரம், அந்த மரத்தில் உள்ள முனைகளில் ஒன்றை உள்ளூர் மூலமாகத் தொடங்கி, அந்த முனை மற்றும் அதன் அனைத்து வழித்தோன்றல்களையும் கொண்டிருக்கும்.

ஒரு முனையின் வழித்தோன்றல்கள் என்பவை அந்த முனையின் அனைத்து குழந்தை முனைகள், அவற்றின் அனைத்து குழந்தை முனைகள், மற்றும் இப்படியே தொடரும் அனைத்து முனைகளும் ஆகும். ஒரு முனையில் இருந்து தொடங்கினால் போதும், அந்த முனையின் கீழே இணைக்கப்பட்டுள்ள அனைத்து முனைகளும் அதன் வழித்தோன்றல்களாகும்.

ஒரு முனையின் உயரம் என்பது அந்த முனைக்கும் ஒரு இலை முனைக்கும் இடையே உள்ள விளிம்புகளின் அதிகபட்ச எண்ணிக்கையாகும்.

ஒரு முனையின் இன்-ஆர்டர் வாரிசு என்பது, நாம் இன்-ஆர்டர் வரிசைப்படுத்தலைச் செய்தால், அதற்குப் பிறகு வரும் முனையாகும். மேலே உள்ள BST-யில் இன்-ஆர்டர் வரிசைப்படுத்தல் செய்தால், முனை 13-க்கு முன் முனை 14 வரும், எனவே முனை 13-இன் வாரிசு முனை 14 ஆகும்.

Traversal of a Binary Search Tree / ஒரு இரும தேடல் மரத்தின் ஊடுருவல்

To check if a Binary Tree is BST, is to do an in-order traversal and check if the resulting list of values are in an increasing order.

ஒரு இரும மரம் BST தானா என்பதைச் சரிபார்க்க, அதில் இன்-ஆர்டர் டிராவர்சல் செய்து, அதன் விளைவாகக் கிடைக்கும் மதிப்புகளின் பட்டியல் ஏறுவரிசையில் உள்ளதா என்பதைச் சரிபார்க்க வேண்டும்.

Example

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

root = TreeNode(13)

node7 = TreeNode(7)

node15 = TreeNode(15)

node3 = TreeNode(3)

node8 = TreeNode(8)

node14 = TreeNode(14)

node19 = TreeNode(19)

node18 = TreeNode(18)

root.left = node7

root.right = node15

node7.left = node3

node7.right = node8

node15.left = node14

node15.right = node19

node19.left = node18

Traverse

inOrderTraversal(root)

Output :

3, 7, 8, 13, 14, 15, 18, 19,

Search for a Value in a BST / ஒரு BST-யில் ஒரு மதிப்பைத் தேடுதல்

How it works:

• Start at the root node.
• If this is the value we are looking for, return.
• If the value we are looking for is higher, continue searching in the right subtree.
• If the value we are looking for is lower, continue searching in the left subtree.
• If the subtree we want to search does not exist, depending on the programming language, return None, or NULL, or something similar, to indicate that the value is not inside the BST.

இது செயல்படும் விதம்:

• மூல முனையிலிருந்து தொடங்கவும்.
• இதுவே நாம் தேடும் மதிப்பாக இருந்தால், அதைத் திருப்பி அனுப்பவும்.
• நாம் தேடும் மதிப்பு அதிகமாக இருந்தால், வலது துணைமரத்தில் தேடுவதைத் தொடரவும்.
• நாம் தேடும் மதிப்பு குறைவாக இருந்தால், இடது துணைமரத்தில் தேடுவதைத் தொடரவும்.
• நாம் தேட விரும்பும் துணைமரம் இல்லை என்றால், நிரலாக்க மொழியைப் பொறுத்து, அந்த மதிப்பு BST-க்குள் இல்லை என்பதைக் குறிக்க None, அல்லது NULL, அல்லது அதுபோன்ற ஒன்றை திருப்பி அனுப்பவும்.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

def search(node, target):

if node is None:

return None

elif node.data == target:

return node

elif target < node.data:

return search(node.left, target)

else:

return search(node.right, target)

root = TreeNode(13)

node7 = TreeNode(7)

node15 = TreeNode(15)

node3 = TreeNode(3)

node8 = TreeNode(8)

node14 = TreeNode(14)

node19 = TreeNode(19)

node18 = TreeNode(18)

root.left = node7

root.right = node15

node7.left = node3

node7.right = node8

node15.left = node14

node15.right = node19

node19.left = node18

Search for a value

result = search(root, 8)

if result:

print(“Found the node with value: {result.data}”)

else:

print(“Value not found in the BST.”)

Output:

Found the node with value: 8

Insert a Node in a BST

How it works:

• Start at the root node.
• Compare each node:
• Is the value lower? Go left.
• Is the value higher? Go right.
• Continue to compare nodes with the new value until there is no right or left to compare with. That is where the new node is inserted.

ஒரு BST-யில் ஒரு முனையைச் செருகுதல்

இது எவ்வாறு செயல்படுகிறது:

• ரூட் முனையிலிருந்து தொடங்கவும்.
• ஒவ்வொரு முனையையும் ஒப்பிட்டுப் பார்க்கவும்:
• மதிப்பு குறைவாக உள்ளதா? இடதுபுறம் செல்லவும்.
• மதிப்பு அதிகமாக உள்ளதா? வலதுபுறம் செல்லவும்.
• ஒப்பிடுவதற்கு வலது அல்லது இடதுபுறம் எதுவும் இல்லாத வரை, புதிய மதிப்புடன் முனைகளை ஒப்பிடுவதைத் தொடரவும். அந்த இடத்தில்தான் புதிய முனை செருகப்படுகிறது.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

def insert(node, data):

if node is None:

return TreeNode(data)

else:

if data < node.data:

node.left = insert(node.left, data)

elif data > node.data:

node.right = insert(node.right, data)

return node

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

root = TreeNode(“Sambar”)

node7 = TreeNode(“Idly”)

node15 = TreeNode(“Tamarind Rice”)

node3 = TreeNode(“Chuttney”)

node8 = TreeNode(“Juice”)

node14 = TreeNode(“Sambal Fish”)

node19 = TreeNode(“Yolk”)

node18 = TreeNode(“Zincovite”)

root.left = node7

root.right = node15

node7.left = node3

node7.right = node8

node15.left = node14

node15.right = node19

node19.left = node18

Inserting new value into the BST

insert(root, “Meals”)

Traverse

inOrderTraversal(root)

Output:

Chuttney, Idlly, Juice, Meals, Sambar, Sambal Fish, Tamarind Rice, Yolk, Zincovite

Find The Lowest Value in a BST Subtree

How it works:

• Start at the root node of the subtree.
• Go left as far as possible.
• The node you end up in is the node with the lowest value in that BST subtree.

ஒரு BST துணைமரத்தில் மிகக் குறைந்த மதிப்பைக் கண்டறிதல்

இது எவ்வாறு செயல்படுகிறது:

• துணைமரத்தின் மூல முனையிலிருந்து தொடங்கவும்.
• முடிந்தவரை இடதுபுறம் செல்லவும்.
• நீங்கள் சென்றடையும் முனைதான் அந்த BST துணைமரத்தில் மிகக் குறைந்த மதிப்பைக் கொண்ட முனையாகும்.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

def insert(node, data):

if node is None:

return TreeNode(data)

else:

if data < node.data:

node.left = insert(node.left, data)

elif data > node.data:

node.right = insert(node.right, data)

return node

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

def minValueNode(node):

current = node

while current.left is not None:

current = current.left

return current

root = TreeNode(“Sambar”)

node7 = TreeNode(“Idly”)

node15 = TreeNode(“Tamarind Rice”)

node3 = TreeNode(“Chuttney”)

node8 = TreeNode(“Juice”)

node14 = TreeNode(“Sambal Fish”)

node19 = TreeNode(“Yolk”)

node18 = TreeNode(“Zincovite”)

root.left = node7

root.right = node15

node7.left = node3

node7.right = node8

node15.left = node14

node15.right = node19

node19.right = node18

Inserting new value into the BST

insert(root, “Meals”)

Traverse

inOrderTraversal(root)

Find Lowest

print(“\nLowest value:”,minValueNode(root).data)

Output:

Chuttney, Idlly, Juice, Meals, Sambar, Sambal Fish, Tamarind Rice, Yolk, Zincovite

Lowest Value: Chuttney

Delete a Node in a BST

How it works:

• If the node is a leaf node, remove it by removing the link to it.
• If the node only has one child node, connect the parent node of the node you want to remove to that child node.
• If the node has both right and left child nodes: Find the node’s in-order successor, change values with that node, then delete it.

ஒரு BST-யில் ஒரு முனையை நீக்குதல்

இது எவ்வாறு செயல்படுகிறது:

• அந்த முனை ஒரு இலை முனையாக இருந்தால், அதற்கான இணைப்பை நீக்குவதன் மூலம் அதை அகற்றவும்.
• அந்த முனைக்கு ஒரே ஒரு குழந்தை முனை மட்டும் இருந்தால், நீங்கள் நீக்க விரும்பும் முனையின் பெற்றோர் முனையை, அந்தக் குழந்தை முனையுடன் இணைக்கவும்.
• அந்த முனைக்கு வலது மற்றும் இடது என இரண்டு குழந்தை முனைகளும் இருந்தால்: அந்த முனையின் இன்-ஆர்டர் வாரிசை (in-order successor) கண்டறிந்து, அந்த முனையுடன் மதிப்புகளைப் பரிமாறிக்கொண்டு, பின்னர் அதை நீக்கவும்.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

def insert(node, data):

if node is None:

return TreeNode(data)

else:

if data < node.data:

node.left = insert(node.left, data)

elif data > node.data:

node.right = insert(node.right, data)

return node

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

def minValueNode(node):

current = node

while current.left is not None:

current = current.left

return current

def delete(node, data):

if not node:

return None

if data < node.data:

node.left = delete(node.left, data)

elif data > node.data:

node.right = delete(node.right, data)

else:

Node with only one child or no child

if not node.left:

temp = node.right

node = None

return temp

elif not node.right:

temp = node.left

node = None

return temp

Node with two children, get the in-order successor

node.data = minValueNode(node.right).data

node.right = delete(node.right, node.data)

return node

root = TreeNode(“Sambar”)

node7 = TreeNode(“Idly”)

node15 = TreeNode(“Tamarind Rice”)

node3 = TreeNode(“Chuttney”)

node8 = TreeNode(“Juice”)

node14 = TreeNode(“Sambal Fish”)

node19 = TreeNode(“Yolk”)

node18 = TreeNode(“Zincovite”)

root.left = node7

root.right = node15

node7.left = node3

node7.right = node8

node15.left = node14

node15.right = node19

node19.right = node18

Inserting new value into the BST

insert(root, “Meals”)

Traverse

inOrderTraversal(root)

Delete node 15

delete(root,”Tamarind Rice”)

Traverse

print() # Creates a new line

inOrderTraversal(root)

Output:

Chuttney, Idlly, Juice, Meals, Sambar, Sambal Fish, Tamarind Rice, Yolk, Zincovite

Chuttney, Idlly, Juice, Meals, Sambar, Sambal Fish, Yolk, Zincovite

Binary Search Trees take the best from two other data structures: Arrays and Linked Lists.

இரும தேடல் மரங்கள் (Binary Search Trees) மற்ற இரண்டு தரவுக் கட்டமைப்புகளான அணிவரிசைகள் மற்றும் இணைக்கப்பட்ட பட்டியல்கள் ஆகியவற்றிலிருந்து சிறந்த அம்சங்களை எடுத்துக்கொள்கின்றன.

A tree is a hierarchical data structure consisting of nodes connected by edges.

Each node contains a value and references to its child nodes.

மரம் என்பது விளிம்புகளால் இணைக்கப்பட்ட முனைகளைக் கொண்ட ஒரு படிநிலைத் தரவுக் கட்டமைப்பாகும்.

ஒவ்வொரு முனையும் ஒரு மதிப்பையும், அதன் குழந்தை முனைகளுக்கான குறிப்புகளையும் கொண்டிருக்கும்.

Binary Trees

A Binary Tree is a type of tree data structure where each node can have a maximum of two child nodes, a left child node and a right child node.

This restriction, that a node can have a maximum of two child nodes, gives us many benefits:

• Algorithms like traversing, searching, insertion and deletion become easier to understand, to implement, and run faster.
• Keeping data sorted in a Binary Search Tree (BST) makes searching very efficient.
• Balancing trees is easier to do with a limited number of child nodes, using an AVL Binary Tree for example.
• Binary Trees can be represented as arrays, making the tree more memory efficient.

இருநிலை மரங்கள்

ஒரு இருநிலை மரம் என்பது ஒரு வகை மரத் தரவுக் கட்டமைப்பாகும், இதில் ஒவ்வொரு முனையத்திற்கும் அதிகபட்சமாக இரண்டு துணை முனைகள் இருக்கலாம், அவை இடது துணை முனை மற்றும் வலது துணை முனை ஆகும்.

ஒரு முனையத்திற்கு அதிகபட்சமாக இரண்டு துணை முனைகள் மட்டுமே இருக்க முடியும் என்ற இந்த வரம்பு, நமக்கு பல நன்மைகளைத் தருகிறது:

• மரம் வழிசெல்லல், தேடல், செருகல் மற்றும் நீக்குதல் போன்ற நெறிமுறைகள் புரிந்துகொள்ளவும், செயல்படுத்தவும் எளிதாகின்றன, மேலும் வேகமாக இயங்குகின்றன.
• ஒரு இருநிலைத் தேடல் மரத்தில் (BST) தரவுகளை வரிசைப்படுத்தி வைப்பது, தேடலை மிகவும் திறமையானதாக ஆக்குகிறது.
• குறைந்த எண்ணிக்கையிலான துணை முனைகளைக் கொண்டு மரங்களைச் சமநிலைப்படுத்துவது எளிது; உதாரணமாக, ஒரு AVL இருநிலை மரத்தைப் பயன்படுத்தலாம்.
• இருநிலை மரங்களை அணிவரிசைகளாகக் குறிப்பிட முடியும், இது மரத்தை நினைவகத் திறனுள்ளதாக்குகிறது.

The Binary Tree above can be implemented much like a Linked List, except that instead of linking each node to one next node, we create a structure where each node can be linked to both its left and right child nodes.

மேலே உள்ள பைனரி மரத்தை ஒரு இணைக்கப்பட்ட பட்டியலைப் போலவே செயல்படுத்தலாம். ஆனால், ஒவ்வொரு முனையையும் அடுத்த ஒரு முனையுடன் இணைப்பதற்குப் பதிலாக, ஒவ்வொரு முனையும் அதன் இடது மற்றும் வலது குழந்தை முனைகள் இரண்டையுமே இணைக்கக்கூடிய ஒரு கட்டமைப்பை நாம் உருவாக்குகிறோம்.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

root = TreeNode(‘MiniTiffin’)

nodeA = TreeNode(‘Dosai’)

nodeB = TreeNode(‘Sambar’)

nodeC = TreeNode(‘Chuttney’)

nodeD = TreeNode(‘Idlly’)

nodeE = TreeNode(‘Kesari’)

nodeF = TreeNode(‘Vadai’)

root.left = nodeA

root.right = nodeB

nodeA.left = nodeC

nodeA.right = nodeD

nodeD.right = nodeE

nodeB.right = nodeF

Test

print(“root.right.left.data:”, root.right.right.data)

Output:

root.right.right.data: Vadai

Types of Binary Trees

There are different variants, or types, of Binary Trees worth discussing to get a better understanding of how Binary Trees can be structured.

A balanced Binary Tree has at most 1 in difference between its left and right subtree heights, for each node in the tree.

A complete Binary Tree has all levels full of nodes, except the last level, which is can also be full, or filled from left to right. The properties of a complete Binary Tree means it is also balanced.

A full Binary Tree is a kind of tree where each node has either 0 or 2 child nodes.

A perfect Binary Tree has all leaf nodes on the same level, which means that all levels are full of nodes, and all internal nodes have two child nodes.The properties of a perfect Binary Tree means it is also full, balanced, and complete.

இருநிலை மரங்களின் வகைகள்

இருநிலை மரங்கள் எவ்வாறு கட்டமைக்கப்படலாம் என்பதைப் பற்றி நன்கு புரிந்துகொள்ள, விவாதிக்கத் தகுந்த இருநிலை மரங்களின் பல்வேறு வகைகள் உள்ளன.

ஒரு சமச்சீர் இருநிலை மரத்தில், மரத்தில் உள்ள ஒவ்வொரு முனையத்திற்கும், அதன் இடது மற்றும் வலது துணை மரங்களின் உயரங்களுக்கு இடையே அதிகபட்சமாக 1 மட்டுமே வேறுபாடு இருக்கும்.

ஒரு முழுமையான இருநிலை மரத்தில், கடைசி நிலை தவிர மற்ற எல்லா நிலைகளிலும் முனைகள் முழுமையாக நிரம்பியிருக்கும். கடைசி நிலையும் முழுமையாக நிரம்பியிருக்கலாம் அல்லது இடமிருந்து வலமாக நிரப்பப்பட்டிருக்கலாம். ஒரு முழுமையான இருநிலை மரத்தின் பண்புகள், அது சமச்சீரானதாகவும் இருப்பதைக் குறிக்கிறது.

ஒரு முழு இருநிலை மரம் என்பது, ஒவ்வொரு முனையும் 0 அல்லது 2 குழந்தை முனைகளைக் கொண்ட ஒரு வகை மரமாகும்.

ஒரு பரிபூரண இருநிலை மரத்தில், அனைத்து இலை முனைகளும் ஒரே மட்டத்தில் இருக்கும். இதன் பொருள், அனைத்து நிலைகளும் முனைகளால் முழுமையாக நிரம்பியிருக்கும், மேலும் அனைத்து உள் முனைகளுக்கும் இரண்டு குழந்தை முனைகள் இருக்கும். ஒரு பரிபூரண இருநிலை மரத்தின் பண்புகள், அது முழுமையானது, சமச்சீரானது மற்றும் முழுமையான இருநிலை மரம் என்பதையும் குறிக்கிறது.

Binary trees that satisfies the following properties for every node:

• The left subtree of the node contains only nodes with keys lesser than the node’s key
• The right subtree of the node contains only nodes with keys greater than the node’s key
• The left and right subtree each must also be a binary search tree.

ஒவ்வொரு முனையத்திற்கும் பின்வரும் பண்புகளைப் பூர்த்தி செய்யும் இருமத் தேடல் மரங்கள்:

• அந்த முனையின் இடது துணைமரம், அந்த முனையின் திறவுகோலை விடச் சிறிய திறவுகோல்களைக் கொண்ட முனைகளை மட்டுமே கொண்டிருக்கும்.
• அந்த முனையின் வலது துணைமரம், அந்த முனையின் திறவுகோலை விடப் பெரிய திறவுகோல்களைக் கொண்ட முனைகளை மட்டுமே கொண்டிருக்கும்.
• இடது மற்றும் வலது துணைமரங்கள் ஒவ்வொன்றும் ஒரு இருமத் தேடல் மரமாகவும் இருக்க வேண்டும்.

In this  article, we focus more on the case where the keys of the nodes are represented by strings and not numbers. In this case, we should first define the ordering of the strings.

Lexicographic ordering is defined as the order that each string that appears in a dictionary. To determine which string is lexicographically larger we compare the corresponding characters of the two strings from left to right. The first character where the two strings differ determines which string comes first. Characters are compared using the Unicode character set and all uppercase letters come before lowercase letters.

இந்தக் கட்டுரையில், நோடுகளின் சாவிகள் எண்களால் அல்லாமல் சரங்களால் குறிப்பிடப்படும் நேர்வில் நாங்கள் அதிக கவனம் செலுத்துகிறோம். இந்த நேர்வில், நாம் முதலில் சரங்களின் வரிசையை வரையறுக்க வேண்டும்.

அகராதியில் ஒவ்வொரு சரமும் தோன்றும் வரிசையே அகரவரிசைப்படி வரிசைப்படுத்துதல் என வரையறுக்கப்படுகிறது. எந்தச் சரம் அகரவரிசைப்படி பெரியது என்பதைக் கண்டறிய, நாம் இரண்டு சரங்களின் தொடர்புடைய எழுத்துக்களை இடமிருந்து வலமாக ஒப்பிடுகிறோம். இரண்டு சரங்களும் வேறுபடும் முதல் எழுத்து, எந்தச் சரம் முதலில் வரும் என்பதைத் தீர்மானிக்கிறது. எழுத்துக்கள் யூனிகோடு எழுத்துத் தொகுப்பைப் பயன்படுத்தி ஒப்பிடப்படுகின்றன, மேலும் அனைத்து பெரிய எழுத்துக்களும் சிறிய எழுத்துக்களுக்கு முன்பாக வருகின்றன.

Binary Tree Traversal

Since Arrays and Linked Lists are linear data structures, there is only one obvious way to traverse these: start at the first element, or node, and continue to visit the next until you have visited them all.

But since a Tree can branch out in different directions (non-linear), there are different ways of traversing Trees.

இருநிலை மரத்தை கடந்து செல்லும் முறைகள்

அரேக்கள் மற்றும் இணைக்கப்பட்ட பட்டியல்கள் நேரியல் தரவு அமைப்புகள் என்பதால், அவற்றை கடந்து செல்ல ஒரே ஒரு தெளிவான வழி மட்டுமே உள்ளது: முதல் உறுப்பு அல்லது முனையத்திலிருந்து தொடங்கி, அனைத்து உறுப்புகளையும் பார்வையிடும் வரை அடுத்தடுத்தவற்றைத் தொடர்ந்து பார்வையிடுவது.

ஆனால் ஒரு மரம் வெவ்வேறு திசைகளில் கிளைக்கக்கூடும் என்பதால் (நேரியல் அல்லாதது), மரங்களைக் கடந்து செல்ல வெவ்வேறு வழிகள் உள்ளன.

A tree is a hierarchical data structure consisting of nodes connected by edges.

Each node contains a value and references to its child nodes.

மரம் என்பது விளிம்புகளால் இணைக்கப்பட்ட முனைகளைக் கொண்ட ஒரு படிநிலைத் தரவுக் கட்டமைப்பாகும்.

ஒவ்வொரு முனையும் ஒரு மதிப்பையும், அதன் குழந்தை முனைகளுக்கான குறிப்புகளையும் கொண்டிருக்கும்.

Trees

The Tree data structure is similar to Linked Lists in that each node contains data and can be linked to other nodes.

Data structures like Arrays, Linked Lists, Stacks, and Queues. These are all linear structures, which means that each element follows directly after another in a sequence. Trees however, are different. In a Tree, a single element can have multiple ‘next’ elements, allowing the data structure to branch out in various directions.

The data structure is called a “tree” because it looks like a tree’s structure.

மரம் (Tree) தரவுக் கட்டமைப்பு, இணைக்கப்பட்ட பட்டியல்களைப் (Linked Lists) போன்றது. ஏனெனில், அதில் ஒவ்வொரு முனையும் தரவைக் கொண்டிருப்பதுடன், மற்ற முனைகளுடன் இணைக்கப்படவும் முடியும்.

அணிகள் (Arrays), இணைக்கப்பட்ட பட்டியல்கள், அடுக்குகள் (Stacks) மற்றும் வரிசைகள் (Queues) போன்ற தரவுக் கட்டமைப்புகள் அனைத்தும் நேரியல் கட்டமைப்புகள் ஆகும். அதாவது, ஒவ்வொரு உறுப்பும் ஒரு வரிசையில் மற்றொன்றைத் தொடர்ந்து நேரடியாக வருகிறது. இருப்பினும், மரங்கள் வேறுபட்டவை. ஒரு மரத்தில், ஒரு தனி உறுப்புக்கு பல ‘அடுத்த’ உறுப்புகள் இருக்க முடியும், இது தரவுக் கட்டமைப்பை பல்வேறு திசைகளில் கிளைத்துச் செல்ல அனுமதிக்கிறது.

இந்தத் தரவுக் கட்டமைப்பு ஒரு மரத்தின் அமைப்பைப் போலவே இருப்பதால், இது “மரம்” என்று அழைக்கப்படுகிறது.

Example / உதாரணம்

The Tree data structure can be useful in many cases:

Hierarchical Data: File systems, organizational models, etc.

Databases: Used for quick data retrieval.

Routing Tables: Used for routing data in network algorithms.

Sorting/Searching: Used for sorting data and searching for data.

Priority Queues: Priority queue data structures are commonly implemented using trees, such as binary heaps.

மரம் (Tree) தரவுக் கட்டமைப்பு பல சந்தர்ப்பங்களில் பயனுள்ளதாக இருக்கும்:

படிநிலைத் தரவு: கோப்பு அமைப்புகள், நிறுவன மாதிரிகள் போன்றவை.

தரவுத்தளங்கள்: தரவை விரைவாக மீட்டெடுக்கப் பயன்படுகிறது.

வழித்தட அட்டவணைகள்: நெட்வொர்க் வழிமுறைகளில் தரவை வழிநடத்தப் பயன்படுகிறது.

வரிசைப்படுத்துதல்/தேடுதல்: தரவை வரிசைப்படுத்தவும், தரவைத் தேடவும் பயன்படுகிறது.

முன்னுரிமை வரிசைகள்: பைனரி ஹீப்ஸ் போன்ற மரங்களைப் பயன்படுத்தி முன்னுரிமை வரிசை தரவுக் கட்டமைப்புகள் பொதுவாகச் செயல்படுத்தப்படுகின்றன.

Types of Trees

Trees are a fundamental data structure in computer science, used to represent hierarchical relationships. This tutorial covers several key types of trees.

Binary Trees: Each node has up to two children, the left child node and the right child node. This structure is the foundation for more complex tree types like Binay Search Trees and AVL Trees.

Binary Search Trees (BSTs): A type of Binary Tree where for each node, the left child node has a lower value, and the right child node has a higher value.

AVL Trees: A type of Binary Search Tree that self-balances so that for every node, the difference in height between the left and right subtrees is at most one. This balance is maintained through rotations when nodes are inserted or deleted.

மரங்களின் வகைகள்

மரங்கள் என்பவை கணினி அறிவியலில் படிநிலைத் தொடர்புகளைக் குறிக்கப் பயன்படும் ஒரு அடிப்படைத் தரவுக் கட்டமைப்பாகும். இந்த வழிகாட்டிப் பாடம் பல முக்கிய மர வகைகளைப் பற்றி விளக்குகிறது.

இருநிலை மரங்கள்: ஒவ்வொரு முனையத்திற்கும் இடது குழந்தை முனை மற்றும் வலது குழந்தை முனை என அதிகபட்சம் இரண்டு குழந்தைகள் இருக்கும். இந்த அமைப்பு, இருநிலை தேடல் மரங்கள் மற்றும் AVL மரங்கள் போன்ற மிகவும் சிக்கலான மர வகைகளுக்கு அடிப்படையாக அமைகிறது.

இருநிலை தேடல் மரங்கள் (BSTகள்): இது ஒரு வகை இருநிலை மரம் ஆகும். இதில் ஒவ்வொரு முனைக்கும், இடது குழந்தை முனையானது குறைந்த மதிப்பையும், வலது குழந்தை முனையானது அதிக மதிப்பையும் கொண்டிருக்கும்.

AVL மரங்கள்: இது ஒரு வகை இருநிலை தேடல் மரம் ஆகும். இது தானாகவே சமநிலைப்படுத்திக் கொள்ளும். இதனால் ஒவ்வொரு முனைக்கும், இடது மற்றும் வலது துணை மரங்களுக்கு இடையிலான உயர வேறுபாடு அதிகபட்சம் ஒன்றாக இருக்கும். முனைகள் சேர்க்கப்படும்போதோ அல்லது நீக்கப்படும்போதோ, சுழற்சிகள் மூலம் இந்தச் சமநிலை பராமரிக்கப்படுகிறது.

Trees vs Arrays and Linked Lists

Benefits of Trees over Arrays and Linked Lists:

• Arrays are fast when you want to access an element directly, like element number 700 in an array of 1000 elements for example. But inserting and deleting elements require other elements to shift in memory to make place for the new element, or to take the deleted elements place, and that is time consuming.

• Linked Lists are fast when inserting or deleting nodes, no memory shifting needed, but to access an element inside the list, the list must be traversed, and that takes time.

• Trees, such as Binary Trees, Binary Search Trees and AVL Trees, are great compared to Arrays and Linked Lists because they are BOTH fast at accessing a node, AND fast when it comes to deleting or inserting a node, with no shifts in memory needed.

மரங்கள் மற்றும் அணிவரிசைகள், இணைக்கப்பட்ட பட்டியல்களுக்கு இடையேயான ஒப்பீடு

அணிவரிசைகள் மற்றும் இணைக்கப்பட்ட பட்டியல்களை விட மரங்களின் நன்மைகள்:

• ஒரு அணிவரிசையில் உள்ள 1000 உறுப்புகளில் 700வது உறுப்பு போன்ற ஒரு உறுப்பை நேரடியாக அணுக விரும்பும்போது, ​​அணிவரிசைகள் வேகமானவை. ஆனால், உறுப்புகளைச் செருகுவதற்கும் நீக்குவதற்கும், புதிய உறுப்பிற்கு இடம் கொடுக்க அல்லது நீக்கப்பட்ட உறுப்பின் இடத்தை நிரப்ப, மற்ற உறுப்புகள் நினைவகத்தில் இடம் மாற வேண்டியுள்ளது, இது அதிக நேரம் எடுக்கும்.

• இணைக்கப்பட்ட பட்டியல்களில் முனைகளைச் செருகும்போது அல்லது நீக்கும்போது வேகம் அதிகமாக இருக்கும், நினைவகத்தில் இடம் மாற்ற வேண்டியதில்லை. ஆனால், பட்டியலில் உள்ள ஒரு உறுப்பை அணுக, பட்டியல் முழுவதையும் கடந்து செல்ல வேண்டும், இதற்கு நேரம் எடுக்கும்.

• பைனரி மரங்கள், பைனரி தேடல் மரங்கள் மற்றும் AVL மரங்கள் போன்ற மரங்கள், அணிவரிசைகள் மற்றும் இணைக்கப்பட்ட பட்டியல்களுடன் ஒப்பிடும்போது சிறந்தவை. ஏனெனில் அவை ஒரு முனையை அணுகுவதிலும் வேகமானவை, மேலும் ஒரு முனையை நீக்குவதிலும் அல்லது செருகுவதிலும் வேகமானவை, இதற்கு நினைவகத்தில் எந்த இட மாற்றமும் தேவையில்லை.

A Hash Table is a data structure designed to be fast to work with.

ஹாஷ் அட்டவணை என்பது வேகமாக வேலை செய்யும் வகையில் வடிவமைக்கப்பட்ட ஒரு தரவு அமைப்பு.

The reason Hash Tables are sometimes preferred instead of arrays or linked lists is because searching for, adding, and deleting data can be done really quickly, even for large amounts of data.

சில நேரங்களில் வரிசைகள் அல்லது இணைக்கப்பட்ட பட்டியல்களுக்குப் பதிலாக ஹாஷ் அட்டவணை விரும்பப்படுவதற்கான காரணம், அதிக அளவிலான தரவுகளுக்குக் கூட தரவைத் தேடுவது, சேர்ப்பது மற்றும் நீக்குவது மிக விரைவாகச் செய்ய முடியும்.

In a Linked List, finding a person “Dosai” takes time because we would have to go from one node to the next, checking each node, until the node with “Dosai” is found.

இணைக்கப்பட்ட பட்டியலில், “தோசை” என்ற நபரைக் கண்டுபிடிப்பதற்கு நேரம் எடுக்கும், ஏனெனில் நாம் ஒரு முனையிலிருந்து அடுத்த முனைக்குச் சென்று, “தோசை” உள்ள முனை காணப்படும் வரை ஒவ்வொரு முனையையும் சரிபார்க்க வேண்டும்.

And finding “Dosai” in an list/array could be fast if we knew the index, but when we only know the name “Dosai”, we need to compare each element and that takes time.

மேலும் ஒரு பட்டியல்/வரிசையில் “தோசை”யைக் கண்டுபிடிப்பது நமக்கு குறியீட்டை அறிந்திருந்தால் வேகமாக இருக்கும், ஆனால் “தோசை” என்ற பெயரை மட்டுமே அறிந்திருக்கும் போது, ​​ஒவ்வொரு உறுப்பையும் ஒப்பிட வேண்டும், அதற்கு நேரம் எடுக்கும்.

With a Hash Table however, finding “Dosai” is done really fast because there is a way to go directly to where “Dosai” is stored, using something called a hash function.

இருப்பினும், ஒரு ஹாஷ் அட்டவணை, “தோசை”யைக் கண்டுபிடிப்பது மிக வேகமாக செய்யப்படுகிறது, ஏனெனில் ஹாஷ் செயல்பாடு எனப்படும் ஒன்றைப் பயன்படுத்தி “தோசை” சேமிக்கப்பட்டுள்ள இடத்திற்கு நேரடியாகச் செல்ல ஒரு வழி உள்ளது.

Hash Table Creation

• Create an empty list (it can also be a dictionary or a set).
• Create a hash function.
• Inserting an element using a hash function.
• Looking up an element using a hash function.
• Handling collisions.

ஹாஷ் அட்டவணை உருவாக்கம்

• ஒரு வெற்றுப் பட்டியலை உருவாக்குதல் (அது ஒரு அகராதியாகவோ அல்லது தொகுப்பாகவோ கூட இருக்கலாம்).
• ஒரு ஹாஷ் சார்பை உருவாக்குதல்.
• ஹாஷ் சார்பைப் பயன்படுத்தி ஒரு உறுப்பைச் சேர்த்தல்.
• ஹாஷ் சார்பைப் பயன்படுத்தி ஒரு உறுப்பைத் தேடுதல்.
• மோதல்களைக் கையாளுதல்.

Create an Empty List /ஒரு வெற்று பட்டியலை உருவாக்கவும்

To keep it simple, let’s create a list with 10 empty elements.

எளிமையாகச் சொல்ல வேண்டுமென்றால், 10 வெற்று கூறுகளைக் கொண்ட பட்டியலை உருவாக்குவோம்.

my_list = [None, None, None, None, None, None, None, None, None, None]

Create a Hash Function / ஒரு ஹாஷ் சார்பு செயல்பாட்டை உருவாக்குதல்

Now comes the special way we interact with Hash Tables.

இப்போது ஹாஷ் அட்டவணைகளுடன் நாம் தொடர்பு கொள்ளும் சிறப்பு வழி வருகிறது.

We want to store a name directly into its right place in the array, and this is where the hash function comes in.

ஒரு பெயரை நேரடியாக வரிசையில் அதன் சரியான இடத்தில் சேமிக்க விரும்புகிறோம், இங்குதான் ஹாஷ் செயல்பாடு வருகிறது.

A hash function can be made in many ways, it is up to the creator of the Hash Table. A common way is to find a way to convert the value into a number that equals one of the Hash Table’s index numbers, in this case a number from 0 to 9.

ஒரு ஹாஷ் செயல்பாட்டை பல வழிகளில் உருவாக்கலாம், அது ஹாஷ் அட்டவணையை உருவாக்கியவரைப் பொறுத்தது. ஒரு பொதுவான வழி, மதிப்பை ஹாஷ் அட்டவணையின் குறியீட்டு எண்களில் ஒன்றிற்கு சமமான எண்ணாக மாற்றுவதற்கான வழியைக் கண்டுபிடிப்பதாகும், இந்த விஷயத்தில் 0 முதல் 9 வரையிலான எண்.

In our example we will use the Unicode number of each character, summarize them and do a modulo 10 operation to get index numbers 0-9.

எங்கள் எடுத்துக்காட்டில், ஒவ்வொரு எழுத்தின் யூனிகோட் எண்ணைப் பயன்படுத்துவோம், அவற்றைச் சுருக்கி, 0-9 குறியீட்டு எண்களைப் பெற மாடுலோ 10 செயல்பாட்டைச் செய்வோம்.

Example / உதாரணம்

def hash_function(value):

sum_of_chars = 0

for char in value:

sum_of_chars += ord(char)

return sum_of_chars % 10

print(“‘Dosai’ has hash code:”, hash_function(‘Dosai’))

Output:

‘Dosai’ has hash code: 6

The character D has Unicode number 68, o has 111,s has 115, a has 97 and i has 105. Adding those together we get 496. Modulo 10 of 496 is 6, so “Dosai” should be stored at index 6.

The number returned by the hash function is called the hash code.

D என்ற எழுத்துக்குறி யூனிகோட் எண் 68, o என்பது 111, s என்பது 115, a என்பது 97 மற்றும் i என்பது 105. இவற்றை ஒன்றாகச் சேர்த்தால் நமக்கு 496 கிடைக்கும். 496 இல் மாடுலோ 10 என்பது 6, எனவே “தோசை” குறியீட்டு 6 இல் சேமிக்கப்பட வேண்டும்.

ஹாஷ் செயல்பாட்டால் வழங்கப்படும் எண் ஹாஷ் குறியீடு என்று அழைக்கப்படுகிறது.

Notes / குறிப்புகள்:

Unicode number: Everything in our computers are stored as numbers, and the Unicode code number is a unique number that exist for every character. For example, the character A has Unicode number 65.

Modulo: A modulo operation divides a number with another number, and gives us the resulting remainder. So for example, 7 % 3 will give us the remainder 1. (Dividing 7 apples between 3 people, means that each person gets 2 apples, with 1 apple to spare.)

In Python and most programming languages, the modolo operator is written as %.

யூனிகோட் எண்: நமது கணினிகளில் உள்ளேஅனைத்தும் எண்களாகவே சேமிக்கப்படுகின்றன, மேலும் யூனிகோட் குறியீட்டு எண் என்பது ஒவ்வொரு எழுத்திற்கும் உள்ள ஒரு தனித்துவமான எண்ணாகும். உதாரணமாக, ‘A’ என்ற எழுத்தின் யூனிகோட் எண் 65 ஆகும்.

மாடுலோ: ஒரு மாடுலோ செயல்பாடு ஒரு எண்ணை மற்றொரு எண்ணால் வகுத்து, அதன் மீதியை நமக்குத் தருகிறது. உதாரணமாக, 7 % 3 என்பது நமக்கு மீதி 1-ஐத் தரும். (7 ஆப்பிள்களை 3 பேருக்குப் பிரித்துக் கொடுத்தால், ஒவ்வொருவருக்கும் 2 ஆப்பிள்கள் கிடைக்கும், மீதி 1 ஆப்பிள் இருக்கும்.)

பைதான் மற்றும் பெரும்பாலான நிரலாக்க மொழிகளில், மாடுலோ செயற்குறி ‘%’ எனக் குறிக்கப்படுகிறது.

Inserting an element

In our hash function, “Dosai” should be stored at index 6.

Lets create a function that add items to our hash table

ஹாஷ் சார்பின்படி, “தோசை” என்ற சொல் 6வது குறியீட்டில் சேமிக்கப்பட வேண்டும்.

இப்போது, ​​நமது ஹாஷ் அட்டவணையில் பொருட்களைச் சேர்க்கும் ஒரு செயற்கூறை உருவாக்குவோம்

my_list = [None, None, None, None, None, None, None, None, None, None]

def hash_function(value):

sum_of_chars = 0

for char in value:

sum_of_chars += ord(char)

return sum_of_chars % 10

def add(name):

index = hash_function(name)

my_list[index] = name

add(‘Dosai’)

print(my_list)

Output:

[None, None, None, None, None, None, ‘Dosai’, None, None, None]

We can use the same functions to store “Pongal”, “Sambar”, “Vadai”, and “Chuttney” as well.

my_list = [None, None, None, None, None, None, None, None, None, None]

def hash_function(value):

sum_of_chars = 0

for char in value:

sum_of_chars += ord(char)

return sum_of_chars % 10

def add(name):

index = hash_function(name)

my_list[index] = name

add(‘Dosai’)

add(‘Pongal’)

add(‘Vadai’)

add(‘Sambar’)

add(‘Chuttney’)

print(my_list)

Output:

[None, None, ‘Chuttney’, None, None, ‘Vadai’, ‘Dosai’, None, ‘Sambar’, ‘Pongal’]

Looking up an element / தரவைத் தேடுகிறது

To find “Dosai” in the Hash Table, we give the name “Dosai” to our hash function. The hash function returns 6, meaning that “Dosai” is stored at index 6.

ஹாஷ் அட்டவணையில் “தோசை”யைக் கண்டறிய, நாம் “தோசை” என்ற பெயரை நமது ஹாஷ் சார்புக்கு வழங்குகிறோம். அந்த ஹாஷ் சார்பு 6 என்ற எண்ணைத் தருகிறது, அதாவது “தோசை” என்பது 6வது குறியீட்டில் சேமிக்கப்பட்டுள்ளது.

my_list = [None, None, None, None, None, None, None, None, None, None]

def hash_function(value):

sum_of_chars = 0

for char in value:

sum_of_chars += ord(char)

return sum_of_chars % 10

def add(name):

index = hash_function(name)

my_list[index] = name

def contains(name):

index = hash_function(name)

return my_list[index] == name

add(‘Dosai’)

add(‘Idlli’)

add(‘Vadai’)

add(‘Sambar’)

add(‘Pongal’)

add(‘Chuttney’)

print(“‘Dosai’ is in the Hash Table:”, contains(‘Dosai’))

Output:

‘Dosai’  is in the Hash Table: True

Handling Collisions / மோதல்களைக் கையாளுதல்

We give “Coffee” to our hash function, which returns 4, meaning “Coffee” should be stored at index 4.

Trying to store “Coffee” in index 4, creates what is called a collision, because “Idlli” is already stored at index 4.

To fix the collision, we can make room for more elements in the same bucket. Solving the collision problem in this way is called chaining, and means giving room for more elements in the same bucket.

நாம் நமது ஹாஷ் ஃபங்ஷனுக்கு “காபி” என்ற உள்ளீட்டைக் கொடுக்கிறோம், அது 4 என்ற எண்ணைத் தருகிறது. அதாவது, “காபி” 4வது இன்டெக்ஸில் சேமிக்கப்பட வேண்டும்.

4வது இன்டெக்ஸில் “காபி”யைச் சேமிக்க முயற்சிக்கும்போது, ​​ஒரு மோதல் (collision) ஏற்படுகிறது, ஏனெனில் அந்த இடத்தில் ஏற்கனவே “இட்லி” சேமிக்கப்பட்டுள்ளது.

இந்த மோதலைச் சரிசெய்ய, அதே பக்கெட்டில் அதிக உறுப்புகளுக்கு இடம் கொடுக்கலாம். இந்த வழியில் மோதல் சிக்கலைத் தீர்ப்பது ‘செயினிங்’ (chaining) என்று அழைக்கப்படுகிறது, மேலும் இது ஒரே பக்கெட்டில் அதிக உறுப்புகளுக்கு இடம் கொடுப்பதைக் குறிக்கிறது.

my_list = [None, None, None, None, None, None, None, None, None, None]

def hash_function(value):

sum_of_chars = 0

for char in value:

sum_of_chars += ord(char)

return sum_of_chars % 10

def add(name):

index = hash_function(name)

my_list[index] = name

add(‘Dosai’)

add(‘Idlli’)

add(‘Vadai’)

add(‘Sambar’)

add(‘Pongal’)

add(‘Chuttney’)

print(my_list)

add(‘Coffee’)

print(my_list)

Output:

[None, None, ‘Chuttney’, None, ‘Idlli’, ‘Vadai’, ‘Dosai’, None, ‘Sambar’, ‘Pongal’]

[None, None, ‘Chuttney’, None, ‘Coffee’, ‘Vadai’, ‘Dosai’, None, ‘Sambar’, ‘Pongal’]

Start by creating a new list with the same size as the original list, but with empty buckets

முதலில், அசல் பட்டியின் அதே அளவுள்ள, ஆனால் காலி பக்கெட்டுகளைக் கொண்ட ஒரு புதிய பட்டியலை உருவாக்குவதன் மூலம் தொடங்கவும்.

my_list = [

[],

[],

[],

[],

[],

[],

[],

[],

[],

[]

]

Example /உதாரணம்

After implementing each bucket as a list, “Coffee” can also be stored at index 4 along with Idlli, and our Hash Set now looks like this:

ஒவ்வொரு பக்கெட்டையும் ஒரு பட்டியலாகச் செயல்படுத்திய பிறகு, இட்லியுடன் சேர்த்து “காபி”யையும் குறியீடு 4-இல் சேமிக்க முடியும், மேலும் இப்போது நமது ஹாஷ் செட் இப்படித் தெரிகிறது:

my_list = [[], [], [], [], [], [], [], [], [], []]

def hash_function(value):

sum_of_chars = 0

for char in value:

sum_of_chars += ord(char)

return sum_of_chars % 10

def add(name):

index = hash_function(name)

my_list[index].append(name)

add(‘Dosai’)

add(‘Idlli’)

add(‘Vadai’)

add(‘Sambar’)

add(‘Pongal’)

add(‘Chuttney’)

add(‘Coffee’)

print(my_list)

Output:

[[], [], [‘Chuttney’], [], [‘Idlli’, ‘Coffee’], [‘Vadai’], [‘Dosai’], [], [‘Sambar’], [‘Pongal’]]

Uses of Hash Tables / ஹாஷ் அட்டவணைகளின் பயன்கள்

Hash Tables are great for:

Checking if something is in a collection (like finding a book in a library).

Storing unique items and quickly finding them (like storing phone numbers).

Connecting values to keys (like linking names to phone numbers).

The most important reason why Hash Tables are great for these things is that Hash Tables are very fast compared Arrays and Linked Lists, especially for large sets. Arrays and Linked Lists have time complexity O(n) for search and delete, while Hash Tables have just O(1) on average.

ஹாஷ் அட்டவணைகள் இதற்கு சிறந்தவை:

ஒரு தொகுப்பில் ஏதாவது இருக்கிறதா என்று சோதித்தல் (நூலகத்தில் ஒரு புத்தகத்தைக் கண்டுபிடிப்பது போல).

தனித்துவமான பொருட்களைச் சேமித்து அவற்றை விரைவாகக் கண்டறிதல் (தொலைபேசி எண்களைச் சேமிப்பது போல).

விசைகளுடன் மதிப்புகளை இணைத்தல் (தொலைபேசி எண்களுடன் பெயர்களை இணைப்பது போல).

இந்த விஷயங்களுக்கு ஹாஷ் அட்டவணைகள் சிறந்ததாக இருப்பதற்கான மிக முக்கியமான காரணம், ஹாஷ் அட்டவணைகள் வரிசைகள் மற்றும் இணைக்கப்பட்ட பட்டியல்களுடன் மிக வேகமாக ஒப்பிடப்படுகின்றன, குறிப்பாக பெரிய தொகுப்புகளுக்கு. வரிசைகள் மற்றும் இணைக்கப்பட்ட பட்டியல்கள் தேட மற்றும் நீக்குவதற்கு நேர சிக்கலான O(n) ஐக் கொண்டுள்ளன, அதே நேரத்தில் ஹாஷ் அட்டவணைகள் சராசரியாக O(1) ஐ மட்டுமே கொண்டுள்ளன.

Summary / சுருக்கம்

Hash Table elements are stored in storage containers called buckets.

A hash function takes the key of an element to generate a hash code.

The hash code says what bucket the element belongs to, so now we can go directly to that Hash Table element: to modify it, or to delete it, or just to check if it exists.

A collision happens when two Hash Table elements have the same hash code, because that means they belong to the same bucket.

Collision can be solved by Chaining by using lists to allow more than one element in the same bucket.

ஹாஷ் அட்டவணையின் கூறுகள் பக்கெட்டுகள் எனப்படும் சேமிப்புக் கொள்கலன்களில் சேமிக்கப்படுகின்றன.

ஒரு ஹாஷ் சார்பு, ஒரு கூறின் சாவியைப் பயன்படுத்தி ஒரு ஹாஷ் குறியீட்டை உருவாக்குகிறது.

அந்த ஹாஷ் குறியீடு, அந்தக் கூறு எந்தப் பக்கெட்டில் உள்ளது என்பதைக் கூறுகிறது. எனவே, நாம் நேரடியாக அந்த ஹாஷ் அட்டவணைக் கூறிற்குச் சென்று, அதை மாற்றியமைக்கலாம், அல்லது நீக்கலாம், அல்லது அது உள்ளதா என்பதைச் சரிபார்க்கலாம்.

இரண்டு ஹாஷ் அட்டவணைக் கூறுகளுக்கு ஒரே ஹாஷ் குறியீடு இருக்கும்போது ஒரு மோதல் ஏற்படுகிறது, ஏனெனில் அது இரண்டும் ஒரே பக்கெட்டில் உள்ளன என்பதைக் குறிக்கிறது.

ஒரே பக்கெட்டில் ஒன்றுக்கு மேற்பட்ட கூறுகளை அனுமதிக்க, பட்டியல்களைப் பயன்படுத்துவதன் மூலம் சங்கிலியிடுதல் முறையில் மோதலைத் தீர்க்கலாம்.

A Linked List is, as the word implies, a list where the nodes are linked together. Each node contains data and a pointer. The way they are linked together is that each node points to where in the memory the next node is placed.

இணைக்கப்பட்ட பட்டியல் என்பது, அந்த வார்த்தை குறிப்பிடுவது போல, முனைகள் ஒன்றாக இணைக்கப்பட்டுள்ள ஒரு பட்டியல். ஒவ்வொரு முனையிலும் தரவு மற்றும் ஒரு சுட்டிக்காட்டி உள்ளது. அவை ஒன்றாக இணைக்கப்பட்டுள்ள விதம் என்னவென்றால், ஒவ்வொரு முனையும் நினைவகத்தில் அடுத்த முனை எங்கு வைக்கப்பட்டுள்ளது என்பதைக் குறிக்கிறது.

Linked Lists

A linked list consists of nodes with data, and a pointer, or link, to the next node.

இணைக்கப்பட்ட பட்டியலில் தரவுகளுடன் கூடிய முனைகளும், அடுத்த முனைக்கான ஒரு சுட்டிக்காட்டி அல்லது இணைப்பும் இருக்கும்.

Types of Linked Lists

• Singly linked lists
• Doubly linked lists
• Circular linked lists

இணைக்கப்பட்ட பட்டியல்களின் வகைகள்

• ஒற்றை இணைக்கப்பட்ட பட்டியல்கள்
• இரட்டை இணைக்கப்பட்ட பட்டியல்கள்
• வட்ட இணைக்கப்பட்ட பட்டியல்கள்

Singly linked lists / ஒற்றை இணைக்கப்பட்ட பட்டியல்கள்

A singly linked list is the simplest kind of linked lists. It takes up less space in memory because each node has only one address to the next node

ஒவ்வொரு முனையும் அடுத்த முனைக்கு ஒரே ஒரு முகவரியை மட்டுமே கொண்டிருப்பதால், இது நினைவகத்தில் குறைந்த இடத்தை எடுத்துக்கொள்கிறது.

Doubly linked lists /இரட்டை இணைக்கப்பட்ட பட்டியல்கள்

A doubly linked list has nodes with addresses to both the previous and the next node, it takes up more memory. But doubly linked lists are good if you want to be able to move both up and down in the list.

இரட்டை இணைக்கப்பட்ட பட்டியலில் முந்தைய மற்றும் அடுத்த முனைகளுக்கான முகவரிகள் கொண்ட முனைகள் உள்ளன, இது அதிக நினைவகத்தை எடுக்கும். ஆனால் பட்டியலில் மேலும் கீழும் நகர்த்த விரும்பினால் இரட்டை இணைக்கப்பட்ட பட்டியல்கள் நல்லது.

Circular linked lists / வட்ட இணைக்கப்பட்ட பட்டியல்கள்

A circular linked list is like a singly or doubly linked list with the first node, the “head”, and the last node, the “tail”, connected.

In singly or doubly linked lists, we can find the start and end of a list by just checking if the links are null. But for circular linked lists, more complex code is needed to explicitly check for start and end nodes in certain applications.

Circular linked lists are good for lists you need to cycle through continuously.

ஒரு வட்ட இணைக்கப்பட்ட பட்டியல் என்பது முதல் முனை, “தலை” மற்றும் கடைசி முனை, “வால்” இணைக்கப்பட்ட ஒற்றை அல்லது இரட்டை இணைக்கப்பட்ட பட்டியலைப் போன்றது.

ஒற்றை அல்லது இரட்டை இணைக்கப்பட்ட பட்டியல்களில், இணைப்புகள் பூஜ்யமாக உள்ளதா என்பதைச் சரிபார்ப்பதன் மூலம் பட்டியலின் தொடக்கத்தையும் முடிவையும் நாம் காணலாம். ஆனால் வட்ட இணைக்கப்பட்ட பட்டியல்களுக்கு, சில பயன்பாடுகளில் தொடக்க மற்றும் முடிவு முனைகளை வெளிப்படையாகச் சரிபார்க்க மிகவும் சிக்கலான குறியீடு தேவைப்படுகிறது.

நீங்கள் தொடர்ந்து சுழற்சி செய்ய வேண்டிய பட்டியல்களுக்கு வட்ட இணைக்கப்பட்ட பட்டியல்கள் நல்லது.

Singly circular

doubly circular

Linked List Operations / இணைக்கப்பட்ட பட்டியல் செயல்பாடுகள்

• Traversal / கடந்து செல்
• Remove a node / ஒரு முனையை அகற்ற
• Insert a node / ஒரு முனையைச் சேர்க்க
• Sort / வரிசைப்படுத்து

Traversal of a Linked List / இணைக்கப்பட்ட பட்டியலின் கடந்து செல்

Traversing a linked list means to go through the linked list by following the links from one node to the next.

Traversal of linked lists is typically done to search for a specific node, and read or modify the node’s content, remove the node, or insert a node right before or after that node.

To traverse a singly linked list, we start with the first node in the list, the head node, and follow that node’s next link, and the next node’s next link and so on, until the next address is null.

இணைக்கப்பட்ட பட்டியலைக் கடந்து செல்வது என்பது ஒரு முனையிலிருந்து அடுத்த முனைக்கு இணைப்புகளைப் பின்பற்றுவதன் மூலம் இணைக்கப்பட்ட பட்டியலைச் சுற்றிச் செல்வதாகும்.

இணைக்கப்பட்ட பட்டியல்களின் வழியாகச் செல்வது பொதுவாக ஒரு குறிப்பிட்ட முனையைத் தேடுவதற்கும், முனையின் உள்ளடக்கத்தைப் படிப்பதற்கும் அல்லது மாற்றுவதற்கும், முனையை அகற்றுவதற்கும் அல்லது அந்த முனைக்கு முன் அல்லது பின் ஒரு முனையைச் செருகுவதற்கும் செய்யப்படுகிறது.

தனித்தனியாக இணைக்கப்பட்ட பட்டியலைக் கடந்து செல்ல, பட்டியலில் உள்ள முதல் முனை, ஹெட் முனையுடன் தொடங்கி, அந்த முனையின் அடுத்த இணைப்பையும், அடுத்த முனையின் அடுத்த இணைப்பையும் பின்தொடர்ந்து, அடுத்த முகவரி முடியும்  வரை தொடர வேண்டும்.

Example / உதாரணம்

class Node:

def init(self, data):

self.data = data

self.next = None

def traverseAndPrint(head):

currentNode = head

while currentNode:

print(currentNode.data, end=” -> “)

currentNode = currentNode.next

print(“null”)

node1 = Node(“Vada”)

node2 = Node(“Idly”)

node3 = Node(“Sambar”)

node4 = Node(“Chuttney”)

node5 = Node(“Kesari”)

node1.next = node2

node2.next = node3

node3.next = node4

node4.next = node5

traverseAndPrint(node1)

Output:

Vada -> Idly -> Sambar -> Chuttney -> Kesari -> null

Delete a Node in a Linked List / இணைக்கப்பட்ட பட்டியலில் ஒரு முனையை நீக்குதல்

If you want to delete a node in a linked list, it is important to connect the nodes on each side of the node before deleting it, so that the linked list is not broken.

So before deleting the node, we need to get the next pointer from the previous node, and connect the previous node to the new next node before deleting the node in between.

Also, it is a good idea to first connect next pointer to the node after the node we want to delete, before we delete it. This is to avoid a ‘dangling’ pointer, a pointer that points to nothing, even if it is just for a brief moment.

The simulation below shows the node we want to delete, and how the list must be traversed first to connect the list properly before deleting the node without breaking the linked list.

இணைக்கப்பட்ட பட்டியலில் உள்ள ஒரு முனையை நீக்க விரும்பினால், அதை நீக்குவதற்கு முன் முனையின் ஒவ்வொரு பக்கத்திலும் உள்ள முனைகளை இணைப்பது முக்கியம், இதனால் இணைக்கப்பட்ட பட்டியல் உடைக்கப்படாது.

எனவே முனையை நீக்குவதற்கு முன், முந்தைய முனையிலிருந்து அடுத்த சுட்டிக்காட்டியைப் பெற வேண்டும், மேலும் இடையில் உள்ள முனையை நீக்குவதற்கு முன் முந்தைய முனையை புதிய அடுத்த முனையுடன் இணைக்க வேண்டும்.

மேலும், அதை நீக்குவதற்கு முன், நாம் நீக்க விரும்பும் முனைக்குப் பிறகு அடுத்த சுட்டிக்காட்டியை முனையுடன் இணைப்பது நல்லது. இது ஒரு ‘தொங்கும்’ சுட்டிக்காட்டியைத் தவிர்ப்பதற்காக, எதையும் சுட்டிக்காட்டாத ஒரு சுட்டிக்காட்டி, அது ஒரு குறுகிய தருணமாக இருந்தாலும் கூட.

கீழே உள்ள உருவகப்படுத்துதல், நாம் நீக்க விரும்பும் முனையையும், இணைக்கப்பட்ட பட்டியலை உடைக்காமல் முனையை நீக்குவதற்கு முன் பட்டியலை சரியாக இணைக்க முதலில் பட்டியலை எவ்வாறு கடக்க வேண்டும் என்பதையும் காட்டுகிறது.

Example / உதாரணம்

class Node:

def init(self, data):

self.data = data

self.next = None

def traverseAndPrint(head):

currentNode = head

while currentNode:

print(currentNode.data, end=” -> “)

currentNode = currentNode.next

print(“null”)

def deleteSpecificNode(head, nodeToDelete):

if head == nodeToDelete:

return head.next

currentNode = head

while currentNode.next and currentNode.next != nodeToDelete:

currentNode = currentNode.next

if currentNode.next is None:

return head

currentNode.next = currentNode.next.next

return head

node1 = Node(“Idly”)

node2 = Node(“Sambar”)

node3 = Node(“Chuttney”)

node4 = Node(“Kesari”)

node1.next = node2

node2.next = node3

node3.next = node4

print(“Before deletion:”)

traverseAndPrint(node1)

Delete node3

node1 = deleteSpecificNode(node1, node3)

print(“\nAfter deletion:”)

traverseAndPrint(node1)

Output:

Before deletion:

Idly -> Sambar -> Chuttney -> Kesari -> null

After deletion:

Idly -> Sambar -> Kesari -> null

Insert a Node in a Linked List / இணைக்கப்பட்ட பட்டியலில் ஒரு முனையைச் சேர்க்கவும்.

Inserting a node into a linked list is very similar to deleting a node, because in both cases we need to take care of the next pointers to make sure we do not break the linked list.

To insert a node in a linked list we first need to create the node, and then at the position where we insert it, we need to adjust the pointers so that the previous node points to the new node, and the new node points to the correct next node.

The simulation below shows how the links are adjusted when inserting a new node.

இணைக்கப்பட்ட பட்டியலில் ஒரு முனையைச் செருகுவது ஒரு முனையை நீக்குவதற்கு மிகவும் ஒத்ததாகும், ஏனெனில் இரண்டு சந்தர்ப்பங்களிலும் இணைக்கப்பட்ட பட்டியலை உடைக்காமல் இருக்க அடுத்த சுட்டிகளை நாம் கவனித்துக் கொள்ள வேண்டும்.

இணைக்கப்பட்ட பட்டியலில் ஒரு முனையைச் செருக, முதலில் முனையை உருவாக்க வேண்டும், பின்னர் அதைச் செருகும் நிலையில், முந்தைய முனை புதிய முனையையும், புதிய முனை சரியான அடுத்த முனையையும் சுட்டிக்காட்டும் வகையில் சுட்டிகளை சரிசெய்ய வேண்டும்.

கீழே உள்ள உருவகப்படுத்துதல் ஒரு புதிய முனையைச் சேர்க்கும்போது இணைப்புகள் எவ்வாறு சரிசெய்யப்படுகின்றன என்பதைக் காட்டுகிறது

New node is created

Node Dosai is linked to new node

New node is linked to next node

புதிய முனை உருவாக்கப்பட்டது

முனை தோசை புதிய முனையுடன் இணைக்கப்பட்டுள்ளது

புதிய முனை அடுத்த முனையுடன் இணைக்கப்பட்டுள்ளது

Example / உதாரணம்

class Node:

def init(self, data):

self.data = data

self.next = None

def traverseAndPrint(head):

currentNode = head

while currentNode:

print(currentNode.data, end=” -> “)

currentNode = currentNode.next

print(“null”)

def insertNodeAtPosition(head, newNode, position):

if position == 1:

newNode.next = head

return newNode

currentNode = head

for _ in range(position – 2):

if currentNode is None:

break

currentNode = currentNode.next

newNode.next = currentNode.next

currentNode.next = newNode

return head

node1 = Node(“Idly”)

node2 = Node(“Sambar”)

node3 = Node(“Chuttney”)

node4 = Node(“Kesari”)

node1.next = node2

node2.next = node3

node3.next = node4

print(“Original list:”)

traverseAndPrint(node1)

Insert a new node with value Dosai at position 4

newNode = Node(“Dosai”)

node1 = insertNodeAtPosition(node1, newNode, 4)

print(“\nAfter insertion:”)

traverseAndPrint(node1)

Output:

Original list:

Idly -> Sambar -> Chuttney -> Kesari -> null

After insertion:

Idly -> Sambar -> Chuttney -> Dosai -> Kesari -> null

Time Complexity of Linked Lists Operations / இணைக்கப்பட்ட பட்டியல் செயல்பாடுகளின் நேர தன்மை

Remember that time complexity just says something about the approximate number of operations needed by the algorithm based on a large set of data (n), and does not tell us the exact time a specific implementation of an algorithm takes.

ஒரு பெரிய தரவுத் தொகுப்பை (n) அடிப்படையாகக் கொண்ட வழிமுறைக்குத் தேவையான செயல்பாடுகளின் தோராயமான எண்ணிக்கையைப் பற்றி  ஏதோ சொல்கிறது என்பதை நினைவில் கொள்ளுங்கள், மேலும் ஒரு வழிமுறையின் குறிப்பிட்ட செயல்படுத்தல் எடுக்கும் சரியான நேரத்தை நமக்குத் தெரிவிக்காது.

This means that even though linear search is said to have the same time complexity for arrays as for linked list: O(n), it does not mean they take the same amount of time. The exact time it takes for an algorithm to run depends on programming language, computer hardware, differences in time needed for operations on arrays vs linked lists, and many other things as well.

அதாவது, நேரியல் தேடல் இணைக்கப்பட்ட பட்டியல் O(n) க்கு அணிவரிசைகளுக்கு அதே நேர தன்மையைக் கொண்டிருப்பதாகக் கூறப்பட்டாலும், அவை அதே அளவு நேரத்தை எடுத்துக்கொள்கின்றன என்று அர்த்தமல்ல. ஒரு வழிமுறை இயங்குவதற்கு எடுக்கும் சரியான நேரம் நிரலாக்க மொழி, கணினி வன்பொருள், வரிசைகள் vs இணைக்கப்பட்ட பட்டியல்களில் செயல்பாடுகளுக்குத் தேவையான நேர வேறுபாடுகள் மற்றும் பல விஷயங்களையும் சார்ந்துள்ளது.

Linear search for linked lists works the same as for arrays. A list of unsorted values are traversed from the head node until the node with the specific value is found. Time complexity is O(n).

இணைக்கப்பட்ட பட்டியல்களுக்கான நேரியல் தேடல் வரிசைகளைப் போலவே செயல்படுகிறது. குறிப்பிட்ட மதிப்புடன் கூடிய முனை கண்டுபிடிக்கப்படும் வரை வரிசைப்படுத்தப்படாத மதிப்புகளின் பட்டியல் தலை முனையிலிருந்து கடந்து செல்கிறது. நேர  O(n) ஆகும்.

Binary search is not possible for linked lists because the algorithm is based on jumping directly to different array elements, and that is not possible with linked lists.

இணைக்கப்பட்ட பட்டியல்களுக்கு பைனரி தேடல் சாத்தியமில்லை, ஏனெனில் வழிமுறை வெவ்வேறு வரிசை கூறுகளுக்கு நேரடியாகத் தாவுவதை அடிப்படையாகக் கொண்டது, மேலும் அது இணைக்கப்பட்ட பட்டியல்களுடன் சாத்தியமில்லை.

Sorting algorithms have the same time complexities as for arrays, and these are explained earlier in this tutorial. But remember, sorting algorithms that are based on directly accessing an array element based on an index, do not work on linked lists.

வரிசைப்படுத்தல் வழிமுறைகள் வரிசைகளுக்கு அதே நேர சிக்கல்களைக் கொண்டுள்ளன, மேலும் இவை இந்த பதிவில் முன்னர் விளக்கப்பட்டுள்ளன. ஆனால் நினைவில் கொள்ளுங்கள், ஒரு குறியீட்டின் அடிப்படையில் ஒரு வரிசை உறுப்பை நேரடியாக அணுகுவதன் அடிப்படையில் வரிசைப்படுத்தும் வழிமுறைகள், இணைக்கப்பட்ட பட்டியல்களில் வேலை செய்யாது.

A map stores data’s  in “key/value” pairs.

ஒரு வரைபடம் தரவை “கீ/மதிப்பு” ஜோடிகளில் சேமிக்கிறது.

Data’s in a map are:

Accessible by keys (not index), and each key is unique.
Automatically sorted in ascending order by their keys.

வரைபடத்தில் உள்ள தரவுகள்:

தெரிகளை (கீஸ்) மூலம் அணுகத்தெரிகின்றன (இண்டெக்ஸ் மூலம் அல்ல), மற்றும் ஒவ்வொரு கீலும் தனித்துவமானது.
அதிகரிக்கும் வரிசையில் தானாகவே தங்கள் கீஸ் மூலம் வரிசைப்படுத்தப்படும்.

Syntax

// Include the map library

Create / Add / Remove Data in Map

To create a map, use the map keyword, and specify the type of both the key and the value it should store within angle brackets <> like map<keytype, valuetype> mapName

To add data’s to a map, it is ok to use square brackets [] or .insert() function.

To remove specific data from a map, you can use the .erase() function

வரைப்படத்தில் தரவை உருவாக்கவும் / சேர்க்கவும் / அகற்றவும்

ஒரு வரைப்பட்டியலை உருவாக்க, map என்ற keyword-ஐ பயன்படுத்தவும், <keytype, valuetype> போன்ற மூலைக்கோணக் குறிகளுக்குள் அதைச் சேமிக்கும் key மற்றும் value வகையையும் குறிப்பிடவும், மற்றும் mapName குறிப்பிடவும்.

வரையறுக்கப்பட்ட தரவுகளை வரைபடத்தில் சேர்க்க கால் செய்ய, சதுரக் கோடிகள் [] அல்லது .insert() செயல்பாட்டைப் பயன்படுத்துவது சரி.

ஒரு வரைபடத்திலிருந்து குறிப்பிட்ட தரவுகளை அகற்ற, நீங்கள் .erase() செயல்பாட்டைப் பயன்படுத்தலாம்

Example / உதாரணம்

#include <iostream>

#include <map>

using namespace std;

int main() {

// Create a map called foods that will store qty ordered

map<string , int> foods = {{“Idly”,2}, {“Vadai”,1}, {“Pongal”,2}, {“Dosa”,1}};

// Add new datas

foods.insert({“Kesari”,1});

foods.insert({“Puttu”,1});

foods[“MasalaDosa”]= 1;

cout << foods.at(“Vadai”) << “\n”;

// Print map datas

for (auto food : foods) {

cout << food.first << ” ordered quantity is: ” << food.second << “\n”;

}

cout << “After Add, now remove data from map” << “\n”;

foods.erase(“Dosa”);

foods.erase(“Puttu”);

for (auto food : foods) {

cout << food.first << ” ordered quantity is: ” << food.second << “\n”;

}

return 0;

}

Output:

Dosa ordered quantity is: 1

Idly ordered quantity is: 2

Kesari ordered quantity is: 1

MasalaDosa ordered quantity is: 1

Pongal ordered quantity is: 2

Puttu ordered quantity is: 1

Vadai ordered quantity is: 1

After Add, now remove data from map

Idly ordered quantity is: 2

Kesari ordered quantity is: 1

MasalaDosa ordered quantity is: 1

Pongal ordered quantity is: 2

Vadai ordered quantity is: 1

Note: The .at() function is often preferred over square brackets [] because it throws an error message if the element does not exist

குறிப்பு: .at() செயல்பாடு பெரும்பாலும் செவ்வகம் [] பதிலாக விரும்பப்படுகிறது, ஏனெனில் அது உருப்படி இல்லாவிட்டால் பிழை செய்தியை உருவாக்குகிறது

Example / உதாரணம்

#include <iostream>

#include <map>

using namespace std;

int main() {

// Create a map called foods that will store qty ordered

map<string , int> foods = {{“Idly”,2}, {“Vadai”,1}, {“Pongal”,2}, {“Dosa”,1}};

// Add new datas

foods.insert({“Kesari”,1});

foods.insert({“Puttu”,1});

foods[“MasalaDosa”]= 1;

//cout << foods[“Juice”] << “\n”;

cout << foods.at(“Juice”) << “\n”;

// Print map datas

for (auto food : foods) {

cout << food.first << ” ordered quantity is: ” << food.second << “\n”;

}

cout << “After Add, now remove data from map” << “\n”;

foods.erase(“Dosa”);

foods.erase(“Puttu”);

for (auto food : foods) {

cout << food.first << ” ordered quantity is: ” << food.second << “\n”;

}

return 0;

}

Output:

terminate called after throwing an instance of ‘std::out_of_range’

what():  map::at

Descriptions

A set stores unique data’s

Data’s is sorted automatically in ascending order.

Data’s is unique, meaning equal or duplicate values are ignored.

Data can be added or removed, but the data of an existing record cannot be changed.

Data order is based on sorting. Index is not supported.

விரிவுரை

ஒரு தொகுப்பு தனித்துவமான தரவைச் சேமிக்கிறது

தரவுகள் தானாகவே ஏறுவரிசையில் வரிசைப்படுத்தப்படுகின்றன.

தரவுகள் தனித்துவமானவை, அதாவது சமமான அல்லது நகல் மதிப்புகள் புறக்கணிக்கப்படும்.

தரவைச் சேர்க்கலாம் அல்லது அகற்றலாம், ஆனால் ஏற்கனவே உள்ள பதிவின் தரவை மாற்ற முடியாது.

தரவு வரிசை வரிசைப்படுத்தலை அடிப்படையாகக் கொண்டது. குறியீட்டுக்கு ஆதரவு இல்லை.

To use a set in C++, you have to include the <set> header file

C++ இல் ஒரு தொகுப்பைப் பயன்படுத்த, நீங்கள் <set> தலைப்பு கோப்பைச் சேர்க்க வேண்டும்.

Syntax

// Include the set library

Create / Add/ Remove Data in Set

If you want to add datas at the time of declaration, place them in a comma-separated list, inside curly braces {}

நீங்கள் அறிவிப்பின் போது தரவுகளைச் சேர்க்க விரும்பினால், அவற்றை வட்டமுள்ள அடெரிகைகளில் {} இடையே காமா கொண்டு பிரிக்கப்பட்ட பட்டியலில் வைக்கவும்

Example / உதாரணம்

#include <iostream>

#include <set>

using namespace std;

int main() {

// Create a set called foods that will store strings data type

set<string> foods = {“Vadai”, “Idly”, “Dosa”, “Poori”};

// Print set data’s

for (string food : foods) {

cout << food << “\n”;

}

return 0;

}

Output

Dosa

Idly

Poori

Vadai

To add data to a set, you can use the .insert() function

ஒரு தொகுதியில் தரவுகளைச் சேர்க்க, நீங்கள் .insert() செயல்பாட்டைப் பயன்படுத்தலாம்

To remove specific data from a set, you can use the .erase() function

ஒரு தொகுதியிலிருந்து குறிப்பிட்ட தரவுகளை நீக்க, நீங்கள் .erase() செயல்பாட்டைப் பயன்படுத்தலாம்

Example / உதாரணம்

#include <iostream>

#include <set>

using namespace std;

int main() {

// Create a set called foods that will store strings

set<string> foods = {“Idly”, “Vadai”, “Pongal”, “Dosa”};

// Add new datas

foods.insert(“Poori”);

foods.insert(“Kesari”);

foods.insert(“Puttu”);

foods.insert(“Dosa”);

// Print set datas

for (string food : foods) {

cout << food << “\n”;

}

cout << “After Add, now remove data from set” << “\n”;

foods.erase(“Dosa”);

foods.erase(“Puttu”);

// Print set datas

for (string food : foods) {

cout << food << “\n”;

}

return 0;

}

Output:

Dosa

Idly

Kesari

Pongal

Poori

Puttu

Vadai

After Add, now remove data from set

Idly

Kesari

Pongal

Poori

Vadai

Feature of set : Unique Data

Data’s in a set are unique, which means they cannot be duplicated or equal.

தொகுப்பு பண்புகள்: தனித்த தன்மை கொண்ட தரவு

தரவுகளின் தொகுப்பில் உள்ளவை தனித்துவமானவை, இதன் அர்த்தம் அவை நகலெடுக்கப்பட முடியாது அல்லது சமமாக இருக்க முடியாது.

Descending Order / இறங்கும் வரிசை

By default, the data’s in a set are sorted in ascending order. If you want the order to be descending, you can use the greater<type> functor inside the angle brackets

பொதுவாக, ஒரு தொகுப்பில் உள்ள தரவு ஏற்முகமான வரிசையில் வரிசைப்படுத்தப்பட்டிருக்கும். நீங்கள் வரிசையை குறைவுபடியாக மாற்ற விரும்பினால், கூண்டுக் கூளக்களில் greater<type> செயலிப்பயன்பாட்டை பயன்படுத்தலாம்.

Example / உதாரணம்

#include <iostream>

#include <set>

using namespace std;

int main() {

// Create a set called foods that will store strings

set<string> foods = {“Idly”, “Vadai”, “Pongal”, “Dosa”};

// Print set datas

for (string food : foods) {

cout << food << “\n”;

}

cout << “After ascending, now displaying set data in reverse” << “\n”;

set<string, greater<string>> revfoods = {“Idly”, “Vadai”, “Pongal”, “Dosa”};

// Print set datas

for (string food : revfoods) {

cout << food << “\n”;

}

return 0;

}

Output :

Dosa

Idly

Pongal

Vadai

After ascending, now displaying set data in reverse

Vadai

Pongal

Idly

Dosa

Descriptions

A deque, is more flexible, as data’s can be added and removed from both ends (at the front and the back). You can also access data’s by index numbers.

To use a deque, you have to include the <deque> header file

விரிவுரை

ஒரு டீக்யூ, அதிக நெகிழ்வானது, ஏனெனில் தரவை இரு முனைகளிலிருந்தும் (முன் மற்றும் பின்புறம்) சேர்க்கலாம் மற்றும் அகற்றலாம். குறியீட்டு எண்கள் மூலமாகவும் தரவை அணுகலாம்.

டீக்யூவைப் பயன்படுத்த, நீங்கள் <deque> தலைப்புக் கோப்பைச் சேர்க்க வேண்டும்.

Syntax

// Include the deque library

Create / Access / Change Deque

Use the deque keyword to create a deque, and specify the type of data’s it should store within angle brackets <> and then the name of the deque, like: deque<type> dequeName.

ஒரு deque ஐ உருவாக்க deque முக்கிய சொல்லைப் பயன்படுத்தவும், மேலும் கோண அடைப்புக்குறிக்குள் அது சேமிக்க வேண்டிய தரவு வகையைக் குறிப்பிடவும், பின்னர் deque இன் பெயரைக் குறிப்பிடவும், அதாவது: deque<type>dequeName.

 deque data’s can be accessed /changed by index, by entering number inside square brackets []

சதுர அடைப்புக்குறிக்குள் எண்ணை உள்ளிடுவதன் மூலம், குறியீட்டு மூலம் deque தரவை அணுகலாம் []

Example / உதாரணம்

#include <iostream>

#include <deque>

using namespace std;

int main() {

deque<string> foods ={“Idly”, “Vadai”} ;

cout<<foods.front(); // Idly

cout<<“\n”;

cout<<foods.at(1); // Outputs Vadai

foods.at(1) = “Dosa”;

cout<<“\n”;

cout<<foods.back(); // Dosa

  return 0;

}

Output :

Idly

Vadai

Dosa

Add/ Change / Remove Deque

use .push_front() to insert a data at the beginning of the deque and .push_back() to add a data at the end

 use .pop_front() to remove a data from the beginning of the deque and .pop_back() to remove a data at the end

 To change the data of a deque, you can refer to the index number

deque-வின் தொடக்கத்தில் ஒரு தரவைச் செருக .push_front() ஐப் பயன்படுத்தவும், இறுதியில் ஒரு தரவைச் சேர்க்க .push_back() ஐப் பயன்படுத்தவும்

deque-வின் தொடக்கத்தில் இருந்து ஒரு தரவை நீக்க .pop_front() ஐப் பயன்படுத்தவும், இறுதியில் ஒரு தரவை நீக்க .pop_back() ஐப் பயன்படுத்தவும்

ஒரு deque-வின் தரவை மாற்ற, நீங்கள் குறியீட்டு எண்ணைப் பார்க்கலாம்.

Example / உதாரணம்

#include <iostream>

#include <deque>

using namespace std;

int main() {

deque<string> foods ={“Idly”, “Vadai”} ;

cout<<foods.front(); // Idly

cout<<“\n”;

cout<<foods.at(1); // Outputs Vadai

foods.at(1) = “Dosa”;

cout<<“\n”;

cout<<foods.back(); // Dosa

foods.push_front(“MasalDosa”);

foods.push_back(“Kesari”);

cout<<“\n”;

cout<<foods.at(0); // MasalDosa

cout<<“\n”;

cout<<foods[2]; //Dosa

cout<<“\n”;

cout<<foods.at(3); // Kesari

  return 0;

}

Output :

Idly

Vadai

Dosa

MasalDosa

Dosa

Kesari

Deque size and empty

To find size of deque, use the .size() function and  to check queue is empty or not use .empty() function returns 1 (true) when deque is empty. 0 (false) when data is in deque.

deque இன் அளவைக் கண்டறிய, .size() செயல்பாட்டைப் பயன்படுத்தவும், வரிசை காலியாக உள்ளதா இல்லையா என்பதைச் சரிபார்க்க, deque காலியாக இருக்கும்போது .empty() செயல்பாட்டைப் பயன்படுத்தவும், deque காலியாக இருக்கும்போது 1 (true) ஐயும், தரவு deque இல் இருக்கும்போது 0 (false) ஐயும் வழங்கும்.

Looping in Deque

you can loop through the deque data’s by using a for loop combined with the .size() function

.size() செயல்பாட்டோடு இணைந்து ஒரு for loop ஐப் பயன்படுத்தி deque தரவை லூப் செய்யலாம்.

Example / உதாரணம்

#include <iostream>

#include <deque>

using namespace std;

int main() {

deque<string> foods ={“Idly”, “Vadai”} ;

cout<<foods.front(); // Idly

cout<<“\n”;

cout<<foods.at(1); // Outputs Vadai

foods.at(1) = “Dosa”;

cout<<“\n”;

cout<<foods.back(); // Dosa

foods.push_front(“MasalDosa”);

foods.push_back(“Kesari”);

cout<<foods.at(0); // MasalDosa

cout<<“\n”;

cout<<foods[2]; //Vadai

cout<<“\n”;

cout<<foods.at(3); // Kesari

cout<<“\n”;

cout<<“Before for loop”;

cout<<“\n”;

for(int i = 0; i < foods.size(); i++) {

  cout << foods[i] << “\n”;

}

  return 0;

}

Output:

Idly

Vadai

DosaMasalDosa

Dosa

Kesari

Before for loop

MasalDosa

Idly

Dosa

Kesari