Binary Search Tree - 1

Binary Search Tree

What Is a Tree ?

• A tree consists of nodes connected by edges.
• The lines (edges) between the nodes represent the way the nodes are related.
• Typically, there is one node in the top row of a tree, with lines connecting to more nodes on the second row, even more on the third, and so on.
• Thus, trees are small on the top and large on the bottom.

Tree Terminology

• Path :
  • Think of someone walking from node to node along the edges that connect them.
• Root :
  • The node at the top of the tree is called the root. There is only one root in a tree.
• Parent :
  • Any node (except the root) has exactly one edge running upward to another node.
• Child :
  • Any node may have one or more lines running downward to other nodes.
• Leaf :
  • A node that has no children is called a leaf node or simply a leaf.
• Subtree :
  • Any node may be considered to be the root of a subtree.
• Visiting :
  • A node is visited when program control arrives at the node, usually for the purpose of carrying out some operation on the node, such as checking the value of one of its data fields or displaying it.
• Traversing :
  • To traverse a tree means to visit all the nodes in some specified order.
• Levels :
  • The level of a particular node refers to how many generations the node is from the root.
• Keys :
  • We’ve seen that one data field in an object is usually designated a key value.

Binary Trees

• If every node in a tree can have at most two children, the tree is called a binary tree.
• The two children of each node in a binary tree are called the left child and the right child.

Binary Search Tree

• A node’s left child must have a key less than its parent.
• A node’s right child must have a key greater than or equal to its parent.

class Node {
    int iData; // data used as key value
    double fData; // other data
    node leftChild; // this node’s left child
    node rightChild; // this node’s right child

	public void displayNode() {
		System.out.print(“{“ + iData + “, “ + fData + “} “);
	}
}

class Tree {
	private Node root; // the only data field in Tree
	
	public void find(int key) {}

	public void insert(int id, double dd) {}

	public void delete(int id) {}

	// various other methods
}

Finding a Node

// find node with given key
public Node find(int key) {
    // while no match
    while(current.iData != key) {
	    // go left?
	    if(key < current.iData) {
		    current = current.leftChild;
	    } else {
		    // or go right?
		    current = current.rightChild; 
	    }
	    // if no child
	    if(current == null) {
		    // didn’t find it
		    return null;
	    }
		
		// found it
		return current; 
    }
}

Finding efficiency for binary search tree

• The time required to find a node depends on how many levels down it is situated.
• O(logN)

Inserting a Node

public void insert(int id, double dd) {
    Node newNode = new Node(); // make new nod
    newNode.iData = id; // insert data
    newNode.dData = dd;
	
	// no node in root
	if(root==null) {
		root = newNode;
	} else { // root occupied
		// start at root
		Node current = root;
		Node parent;
		while(true) {
			parent = current;
			if(id < current.iData) { // go left? 
				current = current.leftChild;
				if(current == null) { // if end of the line, 
					// insert on left
					parent.leftChild = newNode;
					return;
				}
			} else { // or go right?
				current = current.rightChild;
				if(current == null) { // if end of the line 
					// insert on right
					parent.rightChild = newNode;
					return;
				}
			}
		}
	}
}

(未完待續，後續請看 Binary Search Tree - 2)