Binary Search Trees 1

Binary Search Trees 1

1. A tree is an ADT

   • Stores elements hierarchically as nodes: think family tree
   • has a ROOT node and 1 or more subtrees
     • a sub-tree of a node consists of given node and all its descendents(nodes below it)
     • ancestors of a node are all those above it(parent and parent's parents etc
   • each node except ROOT has a parent
   • a node may/may not have children
     • a node with NO children is called a LEAF NODE
   • is a natural organization for data (ubiquitous use)
     • allows algorithms to be implemented much faster than linear ds
   • features
     • degree of node is no. of children it has
     • size of tree: number of nodes in tree
     • depth of a tree: number of links of longest path
     • height of a tree: no. of levels
     • height of node: no of links to furthest descendent
     • depth of node: no of links from root

2. is an ordered binary tree

   • order of children is important
   • used to store data for quick retrieval
     • the tree structure + method if insertion reduce search space when looking for an element

3. binary tree

   • DEF- A binary tree is a finite collection of elements, one of these( if any) is called the root, and the remaining(if any) are partitioned into subtrees, that consist of left-subtree, root and right-subtree
     • degree of node is 2, 1, 0
   • all elements have max of 2 children
   • Each node in Java contains: an element(data), a reference to left child node,a reference to right child
   • maybe empty: no node
   • all paths unique from root to node
   • a full of proper bt: each node 0 or 2 children

4. For each node N, stores an element with a key value K such that - 1. nodes in the left subtree are less than K - 2. nodes in right subtree are greater than K