Yioop - PHP Search Engine

Feb 14 In-Class Exercise.

Post your solutions to the Feb 14 In-Class Exercise to this Thread.

Best, Chris

Post your solutions to the Feb 14 In-Class Exercise to this Thread. Best, Chris

-- Feb 14 In-Class Exercise

Start at the Root. Since 19 > 13, we will use the pointer to the right.

At the next branch, we'll look at the first key value of 23. Since 19 < 23, we will use the pointer to the left.

The following branch contains the key value of 19, and we use the point to get the record associated with the key value 19

(Edited: 2018-02-14)

Start at the Root. Since 19 > 13, we will use the pointer to the right. At the next branch, we'll look at the first key value of 23. Since 19 < 23, we will use the pointer to the left. The following branch contains the key value of 19, and we use the point to get the record associated with the key value 19

-- Feb 14 In-Class Exercise

 k = 19
 Starting at the root, we have the key with value 13. 
 k > 13 and 13 is the only key in this node, so we follow
 the pointer to the right. At this node we have keys 23, 31, 43.
 k < 23 and 23 is the first key, so we follow the pointer to the left.
 This is a leaf node and it contains 13, 17, 19. We have found
 the pointer associated with 19 and we retrieve the record using the pointer.

(Edited: 2018-02-14)

k = 19 Starting at the root, we have the key with value 13. k > 13 and 13 is the only key in this node, so we follow the pointer to the right. At this node we have keys 23, 31, 43. k < 23 and 23 is the first key, so we follow the pointer to the left. This is a leaf node and it contains 13, 17, 19. We have found the pointer associated with 19 and we retrieve the record using the pointer.

-- Feb 14 In-Class Exercise

 13 < K
 K < 23
 K = 19

Would first branch right then left to the 3rd node of the 3rd row. From there, we follow the record pointer under the 19.

(Edited: 2018-02-14)

13 < K K < 23 K = 19 Would first branch right then left to the 3rd node of the 3rd row. From there, we follow the record pointer under the 19.

-- Feb 14 In-Class Exercise

Elena Pearson

1. Node with the 13 (19 is more so go to the right)

2. Node with the 23,31,43 (19 is less than 23 so go to the left)

3. Node with the 13,17,19

Elena Pearson 1. Node with the 13 (19 is more so go to the right) 2. Node with the 23,31,43 (19 is less than 23 so go to the left) 3. Node with the 13,17,19

-- Feb 14 In-Class Exercise

At root 13: 19 > 13, go right to node (23,31,43)
At (23,31,43): 19 < 23, go left to node (13, 17, 19)
At (13, 17, 19): 13 < 19 <= 19, follow the pointer to 19

(Edited: 2018-02-14)

<pre> At root 13: 19 > 13, go right to node (23,31,43) At (23,31,43): 19 < 23, go left to node (13, 17, 19) At (13, 17, 19): 13 < 19 <= 19, follow the pointer to 19 </pre>

-- Feb 14 In-Class Exercise

At top level (node with keys: 13), see that key 19 is greater than key 13, follow pointer to the right.
At middle level (node with keys: 23, 31, 43), see that key 19 is less than key 23, follow pointer to the left.
At bottom level (node with keys: 13, 17, 19), see that key 19 exists in node, follow pointer to record.

(Edited: 2018-02-14)

# At top level (node with keys: 13), see that key 19 is greater than key 13, follow pointer to the right. # At middle level (node with keys: 23, 31, 43), see that key 19 is less than key 23, follow pointer to the left. # At bottom level (node with keys: 13, 17, 19), see that key 19 exists in node, follow pointer to record.

-- Feb 14 In-Class Exercise

To look up the record with key = 19, we first start at the root node (13, (ptrL, ptrR). Since 19 > 13, move to the node ptrR is pointing to (the right one) where we now then have ((23, 31, 43), (ptr1, ptr2, ptr3, ptr4)) as our node to compare. Since 19 < 23, we then will have to access the node ptr1 is pointing to, as such node contains records with key < 23. We are now at the bottom most layer of the tree where 19 is found. Access the actual record pointed by it.

-- Feb 14 In-Class Exercise

   If we start root which is 13
   Since 19 is bigger than 13,  we should search on the right hand path of 13
   From the right hand sub tree, we look at the smallest of the nodes which is 23
   From 23 node, we follow to the left hand sub tree, then pass over one by one there we find the node 19.

(Edited: 2018-02-17)

If we start root which is 13 Since 19 is bigger than 13, we should search on the right hand path of 13 From the right hand sub tree, we look at the smallest of the nodes which is 23 From 23 node, we follow to the left hand sub tree, then pass over one by one there we find the node 19.

-- Feb 14 In-Class Exercise

We’re looking for 19, and the root node has only one search key: 13. Since 19 > 13, we want to follow the pointer to the right of 13.

The next node has search keys 23, 31, and 43; 19 < 23, so we follow the pointer to the left of 23.

The next node has search keys 13, 17, and 19; since 19 = 19, we look at the pointer to the right of 19 and we are done.

(Edited: 2018-02-14)

We’re looking for 19, and the root node has only one search key: 13. Since 19 > 13, we want to follow the pointer to the right of 13. The next node has search keys 23, 31, and 43; 19 < 23, so we follow the pointer to the left of 23. The next node has search keys 13, 17, and 19; since 19 = 19, we look at the pointer to the right of 19 and we are done.