Available Balance
Binary Search Tree – Insertion, Introduction

Binary search trees (BSTs) are very simple to understand. We start with a root node with value x, where the left subtree of x contains nodes with values < x
and the right subtree contains nodes whose values are ¸ x. Each node follows the same rules with respect to nodes in their left and right subtrees. BSTs are of interest because they have operations which are favourably fast: insertion, look up, and deletion can all be done in O(log n) time. It is important to note that the O(log n) times for these operations can only be attained if the BST is reasonably balanced; for a tree data structure with self balancing properties see AVL tree de¯ned in x7).

In the following examples you can assume, unless used as a parameter alias that root is a reference to the root node of the tree.

Insertion

As mentioned previously insertion is an O(log n) operation provided that the tree is moderately balanced.
1) algorithm Insert(value)
2) Pre: value has passed custom type checks for type T
3) Post: value has been placed in the correct location in the tree
4) if root = ; 5) root à node(value)
6) else
7) InsertNode(root, value)
8) end if
9) end Insert

1) algorithm InsertNode(current, value)
2) Pre: current is the node to start from
3) Post: value has been placed in the correct location in the tree
4) if value < current.Value
5) if current.Left = ; 6) current.Left à node(value)
7) else
8) InsertNode(current.Left, value)
9) end if
10) else
11) if current.Right = ; 12) current.Right à node(value)
13) else
14) InsertNode(current.Right, value)
15) end if
16) end if
17) end InsertNode

The insertion algorithm is split for a good reason. The ¯rst algorithm (non- recursive) checks a very core base case – whether or not the tree is empty. If
the tree is empty then we simply create our root node and ¯nish. In all other cases we invoke the recursive InsertNode algorithm which simply guides us to
the ¯rst appropriate place in the tree to put value. Note that at each stage we perform a binary chop: we either choose to recurse into the left subtree or the
right by comparing the new value with that of the current node. For any totally ordered type, no value can simultaneously satisfy the conditions to place it in
both subtrees.

Rate This Content
Linked Lists – Insertion , Searching and more

In general when people talk about insertion with respect to linked lists of any form they implicitly refer to the adding of a node to the tail of the list. When
you use an API like that of DSA and you see a general purpose method that adds a node to the list, you can assume that you are adding the node to the tail
of the list not the head.

Adding a node to a singly linked list has only two cases:
1. head = ; in which case the node we are adding is now both the head and
tail of the list; or
2. we simply need to append our node onto the end of the list updating the
tail reference appropriately.

1) algorithm Add(value)
2) Pre: value is the value to add to the list
3) Post: value has been placed at the tail of the list
4) n à node(value)
5) if head = ; 6) head à n
7) tail à n
8) else
9) tail.Next à n
10) tail à n
11) end if
12) end Add
As an example of the previous algorithm consider adding the following se-
quence of integers to the list: 1, 45, 60, and 12, the resulting list is that of

Figure 2.2.

 

Searching

Searching a linked list is straightforward: we simply traverse the list checking
the value we are looking for with the value of each node in the linked list. The
algorithm listed in this section is very similar to that used for traversal in x2.1.4.

1) algorithm Contains(head, value)
2) Pre: head is the head node in the list
3) value is the value to search for
4) Post: the item is either in the linked list, true; otherwise false
5) n à head
6) while n 6= ; and n.Value 6= value
7) n à n.Next
8) end while
9) if n = ; 10) return false
11) end if
12) return true
13) end Contains

guys for study about physics so let’s join my post and support

physics – http://literacybase.com/physics-study-electric-charges-and-fields/

If you want to for more accounting for begging

so let’s join our accounting post – Introduction to Accounting – Definition, Meaning

Rate This Content