README.md (1877B) - raw
1 # Binary Search Tree 2 3 Welcome to Binary Search Tree on Exercism's Perl 5 Track. 4 If you need help running the tests or submitting your code, check out `HELP.md`. 5 6 ## Instructions 7 8 Insert and search for numbers in a binary tree. 9 10 When we need to represent sorted data, an array does not make a good 11 data structure. 12 13 Say we have the array `[1, 3, 4, 5]`, and we add 2 to it so it becomes 14 `[1, 3, 4, 5, 2]` now we must sort the entire array again! We can 15 improve on this by realizing that we only need to make space for the new 16 item `[1, nil, 3, 4, 5]`, and then adding the item in the space we 17 added. But this still requires us to shift many elements down by one. 18 19 Binary Search Trees, however, can operate on sorted data much more 20 efficiently. 21 22 A binary search tree consists of a series of connected nodes. Each node 23 contains a piece of data (e.g. the number 3), a variable named `left`, 24 and a variable named `right`. The `left` and `right` variables point at 25 `nil`, or other nodes. Since these other nodes in turn have other nodes 26 beneath them, we say that the left and right variables are pointing at 27 subtrees. All data in the left subtree is less than or equal to the 28 current node's data, and all data in the right subtree is greater than 29 the current node's data. 30 31 For example, if we had a node containing the data 4, and we added the 32 data 2, our tree would look like this: 33 34 4 35 / 36 2 37 38 If we then added 6, it would look like this: 39 40 4 41 / \ 42 2 6 43 44 If we then added 3, it would look like this 45 46 4 47 / \ 48 2 6 49 \ 50 3 51 52 And if we then added 1, 5, and 7, it would look like this 53 54 4 55 / \ 56 / \ 57 2 6 58 / \ / \ 59 1 3 5 7 60 61 ## Source 62 63 ### Created by 64 65 - @bentglasstube 66 67 ### Contributed to by 68 69 - @kytrinyx 70 - @m-dango 71 - @rfilipo 72 73 ### Based on 74 75 Josh Cheek - https://twitter.com/josh_cheek