hi I'm Joe James and this video is going to cover binary search trees so a tree is a collection of nodes with edges that connect them the nodes are organized into levels and the top level is called the root node each node can have child nodes in this case the three is a parent node and it has a left child and a right child and the left and right child are called siblings because they share the same parents the 1 4 6 and nine nodes here are called Leaf nodes because they don't have any child
nodes in a binary tree each node can have up to two child nodes a left child and a right child node five's right sub tree includes everything in this triangle which is a tree in itself under node five node 5's left sub tree includes noes 3 1 and four node four has ancestors which are simply every node between itself and the root node and node five has descendants but basically every node below it all of this children node and their children's nodes and so on in a binary search tree each node is greater than every
node in its left sub tree so for example 15 is greater than every node in the left sub tree node 8 is greater than every node in in its left sub tree node 5 is greater than the two in its left sub tree node 24 is greater than 19 in its left sub tree and so on and each node is less than every node in its right sub tree so here we can see that node 15 is less than all the members of its right sub tree 24 is less than the members of its right
sub tree 8 is less than the members of its right sub tree and so on these two characteristics make a binary search tree binary search tree operations we have insert find and delete so for a binary search tree insertion we start at the root which is node 15 let's say we want to insert a 12 we're always going to insert a node as a leaf so our first comparison will compare 12 to 15 12 is less than 15 we take the left child We compare 12 to 8 12 is greater than 8 so we take
the right child We compare 12 12 to 11 12 is greater than 11 so we take the right child we'll compare 12 to 13 and 12 is less than 13 13 has no children so we add 12 as a new left child for note 13 so we can see that node 12 is inserted as a leaf node for the binary search tree find operation we also start at the root let's say we want to find node 19 our first comparison is 19 less than 15 no it is not so we take the right sube is
19 less than 24 yes it is and there we found 19 already so find operation is pretty simple and the binary search tree delete operation there are three possible cases either the node you want to delete is a leaf node it has one child or it has two children and we'll look at each case separately so first let's say we want to delete a node that is a leaf node now in this tree we can see that nodes 2 6 12 19 and 25 are all Leaf nodes so if we want to delete one we
can simply delete it without affecting the rest of the tree now if we want to delete a node that has one child and in our tree example here we can see that nodes 11 13 28 all have one child if we want to delete for example node 11 we can see that 11 is node 8's right child so we make 11's only child 13 eight right child in other words 13 takes 11's place and then we can delete node 11 now note here that node 12 stays attached to this 13's left child and that does
not change it does move up a level in the tree but it stays attached as 13's left child so 13's subtree is not affected now if we want to do a delete operation with two children let's say we want to delete node 24 which we can see has a left child and a right child we find the next higher node so we do that we look at node 24 we follow the right subtree node 28 and then we look at left child and left child continue down the leftmost path until we get to the bottom
in this case there's only one Edge to node 25 so that is the next highest node from 24 so in this case we can change the 24 to 25 and delete note 25 and last case let's say we want to delete a node that has two children in this case node four so four has left child and a right child so first we're going to find the next higher node which is six we changed a four to a six and then we can delete node 6 and since the delete operation is done recursively the seven
basically takes six's place and the six is gone so the advantage of binary search trees speed we can insert delete and find in Big O of H speed which is the Big O of the height of the tree that means that in a balanced binary search tree with 10 million nodes find and certain delete operations take only on the order of 30 comparisons which is incredibly fast that wraps up our introduction to binary search trees I'm Joe James thanks for watching