Lesson Non Linear Data Structures - Artificial Intelligence - ثالث ثانوي

Lesson 3 Non-Linear Data Structures In the previous lessons, you learned about some linear data structures. In linear data structures, each element follows the previous element in a linear manner. Can you think of any case in which things do not proceed linearly? For example, can an element be followed by more than one element? Link to digital lesson www.ien.edu.sa Non-Linear Data Structures A data structure can be characterized by the possibility of linking an element to more than one other element at the same time. An element of a non-linear data structure could be connected to more than one element. Representive examples of non-linear data structures are trees and graphs. Figure 1.33 illustrates the linear and the non-linear data structures. Linear data structure H Non-linear data structure Figure 1.33: Graphical representation of linear and non-linear data structures Table 1.9: Differences between Linear and Non-linear Data Structures Linear Data elements are arranged in a linear order where each element is attached to the previous and the next elements. Data elements can be traversed in a single pass. Implementation is easier. Non-linear Data elements can be attached to many other elements. Data elements cannot be traversed in a single pass. Implementation is more complicated. لالة التعليم Ministry of Education 2024-1446 53

Trees Trees are non-linear data structures. A tree consists of a collection of nodes that are arranged in a hierarchical order. Each node can associate with one or more nodes. Nodes are connected with edges in a form of parent-child relationship. Trees are used in many areas of Computer Science, including operating systems, graphics, database systems, games, Al, and computer networks. Node Edge Figure 1.34: Relationships of a tree Tree Terminology Used in the Tree Data Structure Root: The first and only node in the tree that does not have a parent and is at the first level of the tree. (Node A in figure 1.35) Child: A node directly connected to a node at a higher level. (Node H is the child of node D and nodes B and C are the children of node A) Parent: A node that has one or more children at a lower level. (Node B is the parent of nodes D and E) Leaf: A node that does not have any child nodes. (Node F is a leaf node) Siblings: All child nodes that have the same parent node. (Nodes D and E are siblings) Edges: The links that connect tree nodes. Sub-Tree: Smaller trees that can be found within a larger tree. (A tree with node D as a parent and nodes H and I as children) First level Second level Parent Node Third level Fourth level Н Child Node وزارة التعليم Ministry of Education 54 2024-1446 Root A Edges B C Siblings D E F G Sub-tree Figure 1.35: Tree data structure Tree A tree is a non-linear data structure. It is a collection of nodes arranged hierarchically. Edge An edge connects nodes in a tree data structure. Leaf Node You can have a simple tree, which consists of a single node. This node is also the root of this simple tree, because it has no parent.

Here is an example of a tree data structure. Child Node File Parent Node Vertebrates Root Animals A node can be both a child and a parent: a child of the previous node and a parent of the next node. Invertebrates Birds Fish Mammals Insects Arachnids Camel Horse Tiger Siblings Figure 1.36: Example of a tree data structure Leaf Node Tree Data Structure Features ● They are used to represent a hierarchy. • They are flexible, it is very easy to add or remove an element from a tree. • It is easy to search for an element in a tree. ⚫They reflect structural relationships between the data. Example The organization of files in the operating system is a practical example of a tree. As you can see in figure 1.37, inside the "Documents" folder is another folder called "Python Projects" which contains two other files. This PC Python Projects Home Share View This PC > This PC Documents Python Projects Name 3D Objects Desktop Documents Downloads Music Pictures 3D Objects Desktop Documents Alice Python Projects Downloads Music Pictures وزارة التعليم Ministry of Education 2024-1446 HelloWorld infinite Alice Python Projects HelloWorld.py Figure 1.37: Organization of files in the operating system infinite.py 55

b a e C Figure 1.38: Python dictionary tree Tree Data Structure in Python Python does not provide a predefined data type for the tree data structure. However, trees are easily built out of lists and dictionaries. A very simple implementation of a tree using a dictionary is shown in figure 1.38. In this example, you will create a tree using a Python dictionary. The keys of the dictionary are the nodes of the tree. For each key, the corresponding value is a list containing the nodes that are connected by a direct edge from this node. myTree = { } "a": ["b", "c"], #node "b": ["d", "e"], "C": [None, "f"], "d" [None, None], "e" [None, None], "f" [None, None], print(myTree) d {'a': ['b', 'c'], 'b': ['d', 'e'], 'c': [None, 'f'], 'd' [None, None], 'e': [None, None], 'f': [None, None]} In the following example, you will create a tree like the one in figure 1.39. Parent Children myTree = "Data Structures":["Linear", "Non-linear"], "Linear": ["Stack", "Queue", "Linked List"], "Non-linear": ["Tree", "Graph"]} Data Structures for parent in myTree: print(parent, "has", len(myTree[parent]), "nodes" ) for children in my Tree [parent]: print(" ",children) Data structures has 2 nodes Linear Non-linear Linear has 3 nodes Stack Queue Linked List Non-linear has 2 nodes Tree Graph وزارة التعليم Ministry of Education 56 2024-1446 Linear Non-linear f Tree Graph Stack Queue Linked List Figure 1.39: Data structures tree

Binary Tree There is a special category of trees called binary trees. A binary tree is a tree where each node has two children at most, called Right Child and Left Child. In figure 1.40 you can see an example of a tree and a binary tree. Tree b a d Binary Tree a e f h i j d k g مه E b D h i Left Child Right Child Figure 1.40: Tree and Binary tree Table 1.10: Types of binary tree data structures Description Type Full binary tree Each node, other than "leaves", has either 0 or 2 "children". f g Structure drawing 0 1 2 3 4 Complete Binary Tree Every level of the tree is fully filled, except for possibly the last level. All the nodes in the last level are filled from left to right. 0 1 2 3 4 5 Perfect Binary Tree All internal nodes have two children and all leaves are at the same level. Examples of Applications of Tree Data Structures: Storing hierarchical data, such as folder structures. Defining data in HTML. .implementation of indexing in databasesارت التعليم Ministry of Education 2024-1446 0 1 2 3 4 5 6 57

Decision Tree The decision statement (if a: else b) is one of the most frequently used statements in Python. By nesting and combining these code statements, you can build a decision tree. Decision trees are used in Al through a machine learning technique, called decision tree learning. The end nodes of the trees in this technique, also known as leaves, contain possible solutions to a problem. Each node, with the exception of the leaves, is associated with a logical condition from which the possibilities of answering yes or no branch out. Decision trees are easy to understand, use, visualize, and verify. For example, figure 1.41 shows a decision tree that determines whether to apply for a certain university or not based on two criteria: courses provided by the university and meeting admission requirements. Graphs The most important feature of non-linear data structures is that like arrays and linked lists, their data does not follow a sequence, and its elements can each be associated with more than one element. A rooted tree starts with a root node, which can be connected to other nodes. Trees follow certain rules: the tree nodes must be connected, and the tree must be free of loops and self loops. But what will happen if you don't follow the rules of trees? Then, you are not talking about trees but about a new dynamic data structure called Graphs. In fact, trees are actually a type of graph. The graph is the most general data structure, in the sense that all previous structures presented can be considered special cases of graphs. Figure 1.42 illustrates a graph with six nodes and ten edges. Does the university provide the course I want? Discard No Yes Do my scores meet the admission requirements? Discard No Yes Apply Figure 1.41: Decision tree example Graph A graph is a data structure that consists of a set of nodes and a set of lines that connect all or some of the nodes. A tree is a graph but the reverse is not true as not all graphs are trees. Table 1.11: Differences between Trees and Graphs Trees Nodes attached in hierarchical model. There is a unique node called the root (in rooted trees). Nodes are connected with a parent-child relationship. Graphs 2 1 Nodes attached in network model. There is not a unique or root node. There is no parent-child relationship between the nodes. 5 4 Trees are simpler structures compared to graphs. .ycles are not allowedارة التعليم Graphs are more complex structures. Can contain cycles. 6 Figure 1.42: An example graph with six nodes and ten edges Ministry of Education 58 2024-1446 3

Types of Graphs • Directed Graph: In a directed graph, nodes are connected by directed edges - they only go in one direction. • Undirected graphs: In undirected graphs, the connections have no direction. This means that the edges indicate a two-way relationship where each edge can be traversed in both directions. Figure 1.43 shows a simple directed and undirected graph with six nodes and six edges. Directed Graph Undirected Graph Figure 1.43: Directed and Undirected Graph Graphs in Everyday Life World Wide Web The most representative example of graphs is the World Wide Web. The World Wide Web can be considered as a directed graph, in which the vertices represent web pages and the directed edges the hyperlinks. Web structure mining is the discovery of useful knowledge from the structure of the World Wide Web represented though hyperlinks. A person can form a graph structure of such hyperlinks and the relationships they create between different web pages. You can see a graphical representation of the World Wide Web in figure 1.44. By accessing such graphs, someone can calculate the relative importance of a web page. A B C D B D Figure 1.44: World Wide Web D C The Google search engine uses a similar approach to find the relative importance of a web page and orders the search result according to this importance. The algorithm used by Google is known as the PageRank algorithm and was invented by the Google founders. وزارة التعليم Ministry of Education 2024-1446 59

Facebook Facebook is another example of an undirected graph. As you can see in figure 1.46, the nodes represent Facebook users, while the edges represent friendship relationships. When you want to add a friend, he or she has to accept your request; that person cannot be your friend on the network without accepting your friend request. The relationship here between two users (two nodes) is a two-way relationship. Facebook's friend suggestion algorithm uses graph theory. Social network analysis studies social relationships using graphs or network theory from Computer Science. User Friendship Relationship Google Maps Figure 1.46: Facebook's undirected graph Google maps and all other similar applications use graphs for showing transportation systems to calculate the shortest path between two locations. These applications use graphs that contain a very large number of nodes and edges that cannot be distinguished by the human eye. Panama M a te Ma Riyadh 21mm 12m AIN P Altham Ma AR RAZIAN CARM Neural Network Figure 1.45: Google maps A neural network is a machine learning graph that imitates the human brain. A neural network can be directed or undirected depending on the learning objective. It consists of neurons and weights distributed in different layers. The neurons are represented by nodes, and the weights are represented by edges. Signal flows are computed and optimized throughout the neural network structure to minimize error. Neural networks are used in many intelligent applications such as machine translation, image classification, object detection, and object recognition. Figure 1.47 shows an example of a neural network structure. وزارة التعليم Ministry of Education 60 2024-1446 input layer hidden layers output layer Figure 1.47: Neural Network Structure

Graphs in Python Since Python does not provide a predefined data type for trees, it also does not provide a predefined data type for graphs (remember that trees are a special case of graphs). However, graphs can also be built out of lists and dictionaries. In the following example, you will do the following: 1. Create a directed graph like the one shown in figure 1.48. 2. Create a function to add a node to the graph. 3. Create an object containing all paths of the graph. myGraph "I = { a" : ["b","c"], "b" : ["c", "d"], "c" : ["d", "e"], "d" : [], "e" : [], } print(myGraph) d b a Figure 1.48: Graph example e {'a': ['b', 'c'], 'b': ['c', 'd'], 'c': ['d', 'e'], 'd' [], 'e': []} Then the main program will: 1. Create the graph. 2. Print the graph. 3. Call the add function. 4. Print all the graph's paths. You will use a dictionary whose keys are the nodes of the graph. For each key, the corresponding value will be a list containing nodes connected by a direct edge of this node. #function for adding an edge to a graph def addEdge(graph, u,v): graph[u].append(v) #function for generating the edges of a graph def generate_edges(graph): edges = [] # for each node in graph for node in graph: #for each neighbouring node of a single node for neighbour in graph[node]: وزارة التعليم Ministry of Education 2024-1446 61

# if edge exists then append to the list edges.append((node, neighbour)) return edges # main program #initialisation of graph as dictionary myGraph {"a": ["b","c"], = } "b" ["c", "d"], "c" ["d", "e"], : "d" : [], "e" : [], # print the graph contents print("The graph contents") print(generate_edges(myGraph)) # add more edges to the graph addEdge(myGraph, 'a', 'e') addEdge (myGraph, 'c', 'f') # print the graph after adding new edges print("The new graph after adding new edges") print(generate_edges (myGraph)) The graph contents [('a', 'b'), ('a', 'c'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('c', 'e')] The new graph after adding new edges. [('a', 'b'), ('a', 'c'), ('a', 'e'), ('b', 'c'), ('b', 'd'), ('c', 'd'), ('c', 'e'), ('c', 'f')] وزارة التعليم Ministry of Education 62 2024-1446

1 2 Exercises Read the sentences and tick ✓ True or False. 1. An element in a nonlinear data structure could be connected to more than one element. 2. The implementation of linear data structures is more complicated than the implementation of nonlinear data structures. 3. In decision tree learning, the leaves contain the answers to a problem. 4. The Google PageRank algorithm calculates the relative importance of a web page on the World Wide Web. 5. Neural networks are a graph used to visualize other problems. State the difference between trees and graphs. Trees Graphs True False 3 Describe how graph algorithms are utilized in commercial applications. وزارة التعليم Ministry of Education 2024-1446 63

4 Fill in the blanks with the correct names of the parts of the tree. C وزارة التعليم Ministry of Education 64 2024-1446 b d a f مه g j k e h

5 In the following image, you can see a book's contents page. • Complete its tree representation. وزارة التعليم Ministry of Education 2024-1446 Book C1 C1.1 C1.2 C2. C1.1 C2.1 C2.1.1 C2.1.2. C2.2. C2.3 C3 Is it a binary tree? Justify your answer. C1 Book C2 65

6 Draw the tree that will result from the following information: • Node A has children B and C. • Node D and E have the same parent which is node B. • Node F has a sibling which is node G, and they have the same parent which is node C. • Node H has two child nodes, I and J, and has a parent, node F. What type of tree is described above? وزارة التعليم Ministry of Education 66 2024-1446

Using the dictionary in Python, write the appropriate program to represent this tree and print the parents and children. وزارة التعليم Ministry of Education 2024-1446 67