Binary Search Tree

• A search tree is a data structures that support many dynamic-set operations.Includes operations SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE. Thus a search tree can be used both as a dictionary and as a priority queue
• Can be used as both a dictionary and as a priority queue.
• Basic operations take time proportional to the height of the tree.
• For complete binary tree with n nodes: worst case (lg n).
• For linear chain of n nodes: worst case (n).

Properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

Advantages:

The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Applications:

Binary search trees are a fundamental data structure used to construct more abstract data structures such as :

1.sets

2. multi sets

3. associative arrays.

Types:

There are many types of binary search trees. 

1.AVL trees 

2.red-black trees 

They are both forms of self-balancing binary search trees. 

Two other titles describing binary search trees are that of a complete and degenerate tree.

A complete tree is a tree with n levels, where for each level d <= n - 1, the number of existing nodes at level d is equal to 2^d. This means all possible nodes exist at these levels. An additional requirement for a complete binary tree is that for the nth level, while every node does not have to exist, the nodes that do exist must fill from left to right.

A degenerate tree is a tree where for each parent node, there is only one associated child node. What this means is that in a performance measurement, the tree will essentially behave like a linked list data structure.

Working with Binary Search Tree:

Binary search trees are an important data structure for dynamic sets.

• Accomplish many dynamic-set operations in O(h) time, where h = height of tree.

• We can  represent a binary tree by a linked data structure in which each node is an object.

• root[T ] points to the root of tree T .

• Each node contains the fields

• key (and possibly other satellite data).

• left: points to left child.

• right: points to right child.

• p: points to parent. p[root[T ]] = NIL.

• Stored keys must satisfy the binary-search-tree property.

• If y is in left subtree of x, then key[y] ≤ key[x].

• If y is in right subtree of x, then key[y] ≥ key[x].

The binary-search-tree property allows us to print keys in a binary search tree in

order, recursively, using an algorithm called an inorder tree walk. Elements are

printed in monotonically increasing order.

How INORDER-TREE-WALK works:

• Check to make sure that x is not NIL.

• Recursively, print the keys of the nodes in x’s left subtree.

• Print x’s key.

• Recursively, print the keys of the nodes in x’s right subtree.

INORDER-TREE-WALK(x)

if x = NIL

then INORDER-TREE-WALK(left[x])

print key[x]

INORDER-TREE-WALK(right[x])

Operations:

1. Searching

Searching a binary search tree for a specific value can be a recursive or iterative process. This explanation covers a recursive method.

We begin by examining the root node. If the tree is null, the value we are searching for does not exist in the tree. Otherwise, if the value equals the root, the search is successful. If the value is less than the root, search the left subtree. Similarly, if it is greater than the root, search the right subtree. This process is repeated until the value is found or the indicated subtree is null. If the searched value is not found before a null subtree is reached, then the item must not be present in the tree.

Searching

TREE-SEARCH(x, k)

if x = NIL or k = key[x]

then return x

if k < key[x]

then return TREE-SEARCH(left[x], k)

else return TREE-SEARCH(right[x], k)

Initial call is TREE-SEARCH(root[T ], k).

2. Insertion

Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.

TREE-INSERT(T, z)

y ← NIL

x ← root[T ]

while x = NIL

do y ← x

if key[z] < key[x]

then x ← left[x]

else x ← right[x]

p[z] ← y

if y = NIL

then root[T ] ← z Tree T was empty

else if key[z] < key[y]

then left[y] ← z

else right[y] ← z

• To insert value v into the binary search tree, the procedure is given node z, with

key[z] = v, left[z] = NIL, and right[z] = NIL.

• Beginning at root of the tree, trace a downward path, maintaining two pointers.

• Pointer x: traces the downward path.

• Pointer y: “trailing pointer” to keep track of parent of x.

• Traverse the tree downward by comparing the value of node at x with v, and

move to the left or right child accordingly.

• When x is NIL, it is at the correct position for node z.

• Compare z’s value with y’s value, and insert z at either y’s left or right, appropriately.

3. Deletion

There are three possible cases to consider:

• Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
• Deleting a node with one child: Remove the node and replace it with its child.
• Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node,R. Replace the value of N with the value of R, then delete R.

TREE-DELETE(T, z)

Determine which node y to splice out: either z or z’s successor.

if left[z] = NIL or right[z] = NIL

then y ← z

else y ← TREE-SUCCESSOR(z)

x is set to a non-NIL child of y, or to NIL if y has no children.

if left[y] = NIL

then x ← left[y]

else x ← right[y]

y is removed from the tree by manipulating pointers of p[y] and x.

if x = NIL

then p[x] ← p[y]

if p[y] = NIL

then root[T ] ← x

else if y = left[p[y]]

then left[p[y]] ← x

else right[p[y]] ← x

If it was z’s successor that was spliced out, copy its data into z.

if y = z

then key[z] ← key[y]

copy y’s satellite data into z

return y

4. Traversal

Once the binary search tree has been created, its elements can be retrieved in-order by recursively traversing the left subtree of the root node, accessing the node itself, then recursively traversing the right subtree of the node, continuing this pattern with each node in the tree as it's recursively accessed. As with all binary trees, one may conduct a pre-order traversal or a post-order traversal, but neither are likely to be useful for binary search trees.

How INORDER-TREE-WALK works:

• Check to make sure that x is not NIL.

• Recursively, print the keys of the nodes in x’s left subtree.

• Print x’s key.

• Recursively, print the keys of the nodes in x’s right subtree.

INORDER-TREE-WALK(x)

if x = NIL

then INORDER-TREE-WALK(left[x])

print key[x]

INORDER-TREE-WALK(right[x])