BTree算法

BTree算法

作者：cleverpig

注释：由于BTree可用于j2me、DB等query场景中，而且原理易懂，自此就不做翻译了。




What's B-Tree


Sample B-Tree


Tree structures support various basic dynamic set operations including Search, Predecessor, Successor, Minimum, Maximum, Insert, and Delete in time proportional to the height of the tree. Ideally, a tree will be balanced and the height will be log n where n is the number of nodes in the tree. To ensure that the height of the tree is as small as possible and therefore provide the best running time, a balanced tree structure like a red-black tree, AVL tree, or b-tree must be used.

When working with large sets of data, it is often not possible or desirable to maintain the entire structure in primary storage (RAM). Instead, a relatively small portion of the data structure is maintained in primary storage, and additional data is read from secondary storage as needed. Unfortunately, a magnetic disk, the most common form of secondary storage, is significantly slower than random access memory (RAM). In fact, the system often spends more time retrieving data than actually processing data.

B-trees are balanced trees that are optimized for situations when part or all of the tree must be maintained in secondary storage such as a magnetic disk. Since disk accesses are expensive (time consuming) operations, a b-tree tries to minimize the number of disk accesses. For example, a b-tree with a height of 2 and a branching factor of 1001 can store over one billion keys but requires at most two disk accesses to search for any node.



Searching a B-Tree for Key 21

Inserting Key 33 into a B-Tree (w/ Split)


Java Binary Trees and Solutions

In Java, the key points in the recursion are exactly the same as in C or C++. In fact, I created the Java solutions by just copying the C solutions, and then making the syntactic changes. The recursion is the same, however the outer structure is slightly different.

In Java, we will have a BinaryTree object that contains a single root pointer. The root pointer points to an internal Node class that behaves just like the node struct in the C/C++ version. The Node class is private -- it is used only for internal storage inside the BinaryTree and is not exposed to clients. With this OOP structure, almost every operation has two methods: a one-line method on the BinaryTree that starts the computation, and a recursive method that works on the Node objects. For the lookup() operation, there is a BinaryTree.lookup() method that the client uses to start a lookup operation. Internal to the BinaryTree class, there is a private recursive lookup(Node) method that implements the recursion down the Node structure. This second, private recursive method is basically the same as the recursive C/C++ functions above -- it takes a Node argument and uses recursion to iterate over the pointer structure.

Java Binary Tree Structure

To get started, here are the basic definitions for the Java BinaryTree class, and the lookup() and insert() methods as examples...

// BinaryTree.java 
public class BinaryTree { 
  // Root node pointer. Will be null for an empty tree. 
  private Node root; 
  
  /* 
   --Node-- 
   The binary tree is built using this nested node class. 
   Each node stores one data element, and has left and right 
   sub-tree pointer which may be null. 
   The node is a "dumb" nested class -- we just use it for 
   storage; it does not have any methods. 
  */ 
  private static class Node { 
    Node left; 
    Node right; 
    int data; 
    Node(int newData) { 
      left = null; 
      right = null; 
      data = newData; 
    } 
  } 
  /** 
   Creates an empty binary tree -- a null root pointer. 
  */ 
  public void BinaryTree() { 
    root = null; 
  } 
  
  /** 
   Returns true if the given target is in the binary tree. 
   Uses a recursive helper. 
  */ 
  public boolean lookup(int data) { 
    return(lookup(root, data)); 
  } 
  
  /** 
   Recursive lookup  -- given a node, recur 
   down searching for the given data. 
  */ 
  private boolean lookup(Node node, int data) { 
    if (node==null) { 
      return(false); 
    } 
    if (data==node.data) { 
      return(true); 
    } 
    else if (data<node.data) { 
      return(lookup(node.left, data)); 
    } 
    else { 
      return(lookup(node.right, data)); 
    } 
  } 
  
  /** 
   Inserts the given data into the binary tree. 
   Uses a recursive helper. 
  */ 
  public void insert(int data) { 
    root = insert(root, data); 
  } 
  
  /** 
   Recursive insert -- given a node pointer, recur down and 
   insert the given data into the tree. Returns the new 
   node pointer (the standard way to communicate 
   a changed pointer back to the caller). 
  */ 
  private Node insert(Node node, int data) { 
    if (node==null) { 
      node = new Node(data); 
    } 
    else { 
      if (data <= node.data) { 
        node.left = insert(node.left, data); 
      } 
      else { 
        node.right = insert(node.right, data); 
      } 
    } 
    return(node); // in any case, return the new pointer to the caller 
  } 

OOP Style vs. Recursive Style

From the client point of view, the BinaryTree class demonstrates good OOP style -- it encapsulates the binary tree state, and the client sends messages like lookup() and insert() to operate on that state. Internally, the Node class and the recursive methods do not demonstrate OOP style. The recursive methods like insert(Node) and lookup (Node, int) basically look like recursive functions in any language. In particular, they do not operate against a "receiver" in any special way. Instead, the recursive methods operate on the arguments that are passed in which is the classical way to write recursion. My sense is that the OOP style and the recursive style do not be combined nicely for binary trees, so I have left them separate. Merging the two styles would be especially awkward for the "empty" tree (null) case, since you can't send a message to the null pointer. It's possible to get around that by having a special object to represent the null tree, but that seems like a distraction to me. I prefer to keep the recursive methods simple, and use different examples to teach OOP.

Java Solutions

Here are the Java solutions to the 14 binary tree problems. Most of the solutions use two methods:a one-line OOP method that starts the computation, and a recursive method that does the real operation. Make an attempt to solve each problem before looking at the solution -- it's the best way to learn.

1. Build123() Solution (Java)

/** 
 Build 123 using three pointer variables. 
*/ 
public void build123a() { 
  root = new Node(2); 
  Node lChild = new Node(1); 
  Node rChild = new Node(3); 
  root.left = lChild; 
  root.right= rChild; 
} 
/** 
 Build 123 using only one pointer variable. 
*/ 
public void build123b() { 
  root = new Node(2); 
  root.left = new Node(1); 
  root.right = new Node(3); 
} 
  
/** 
 Build 123 by calling insert() three times. 
 Note that the '2' must be inserted first. 
*/ 
public void build123c() { 
  root = null; 
  root = insert(root, 2); 
  root = insert(root, 1); 
  root = insert(root, 3); 
} 

2. size() Solution (Java)

/** 
 Returns the number of nodes in the tree. 
 Uses a recursive helper that recurs 
 down the tree and counts the nodes. 
*/ 
public int size() { 
  return(size(root)); 
} 
private int size(Node node) { 
  if (node == null) return(0); 
  else { 
    return(size(node.left) + 1 + size(node.right)); 
  } 
} 

3. maxDepth() Solution (Java)

/** 
 Returns the max root-to-leaf depth of the tree. 
 Uses a recursive helper that recurs down to find 
 the max depth. 
*/ 
public int maxDepth() { 
  return(maxDepth(root)); 
} 
private int maxDepth(Node node) { 
  if (node==null) { 
    return(0); 
  } 
  else { 
    int lDepth = maxDepth(node.left); 
    int rDepth = maxDepth(node.right); 
    // use the larger + 1 
    return(Math.max(lDepth, rDepth) + 1); 
  } 
} 

4. minValue() Solution (Java)

/** 
 Returns the min value in a non-empty binary search tree. 
 Uses a helper method that iterates to the left to find 
 the min value. 
*/ 
public int minValue() { 
 return( minValue(root) ); 
} 
  
/** 
 Finds the min value in a non-empty binary search tree. 
*/ 
private int minValue(Node node) { 
  Node current = node; 
  while (current.left != null) { 
    current = current.left; 
  } 
  return(current.data); 
} 

5. printTree() Solution (Java)

/** 
 Prints the node values in the "inorder" order. 
 Uses a recursive helper to do the traversal. 
*/ 
public void printTree() { 
 printTree(root); 
 System.out.println(); 
} 
private void printTree(Node node) { 
 if (node == null) return; 
 // left, node itself, right 
 printTree(node.left); 
 System.out.print(node.data + "  "); 
 printTree(node.right); 
} 

6. printPostorder() Solution (Java)

/** 
 Prints the node values in the "postorder" order. 
 Uses a recursive helper to do the traversal. 
*/ 
public void printPostorder() { 
 printPostorder(root); 
 System.out.println(); 
} 
public void printPostorder(Node node) { 
  if (node == null) return; 
  // first recur on both subtrees 
  printPostorder(node.left); 
  printPostorder(node.right); 
  // then deal with the node 
 System.out.print(node.data + "  "); 
} 

7. hasPathSum() Solution (Java)

/** 
 Given a tree and a sum, returns true if there is a path from the root 
 down to a leaf, such that adding up all the values along the path 
 equals the given sum. 
 Strategy: subtract the node value from the sum when recurring down, 
 and check to see if the sum is 0 when you run out of tree. 
*/ 
public boolean hasPathSum(int sum) { 
 return( hasPathSum(root, sum) ); 
} 
boolean hasPathSum(Node node, int sum) { 
  // return true if we run out of tree and sum==0 
  if (node == null) { 
    return(sum == 0); 
  } 
  else { 
  // otherwise check both subtrees 
    int subSum = sum - node.data; 
    return(hasPathSum(node.left, subSum) || hasPathSum(node.right, subSum)); 
  } 
} 

8. printPaths() Solution (Java)

/** 
 Given a binary tree, prints out all of its root-to-leaf 
 paths, one per line. Uses a recursive helper to do the work. 
*/ 
public void printPaths() { 
  int[] path = new int[1000]; 
  printPaths(root, path, 0); 
} 
/** 
 Recursive printPaths helper -- given a node, and an array containing 
 the path from the root node up to but not including this node, 
 prints out all the root-leaf paths. 
*/ 
private void printPaths(Node node, int[] path, int pathLen) { 
  if (node==null) return; 
  // append this node to the path array 
  path[pathLen] = node.data; 
  pathLen++; 
  // it's a leaf, so print the path that led to here 
  if (node.left==null && node.right==null) { 
    printArray(path, pathLen); 
  } 
  else { 
  // otherwise try both subtrees 
    printPaths(node.left, path, pathLen); 
    printPaths(node.right, path, pathLen); 
  } 
} 
/** 
 Utility that prints ints from an array on one line. 
*/ 
private void printArray(int[] ints, int len) { 
  int i; 
  for (i=0; i<len; i++) { 
   System.out.print(ints[i] + " "); 
  } 
  System.out.println(); 
} 

9. mirror() Solution (Java)

/** 
 Changes the tree into its mirror image. 
 So the tree... 
       4 
      / \ 
     2   5 
    / \ 
   1   3 
 is changed to... 
       4 
      / \ 
     5   2 
        / \ 
       3   1 
 Uses a recursive helper that recurs over the tree, 
 swapping the left/right pointers. 
*/ 
public void mirror() { 
  mirror(root); 
} 
private void mirror(Node node) { 
  if (node != null) { 
    // do the sub-trees 
    mirror(node.left); 
    mirror(node.right); 
    // swap the left/right pointers 
    Node temp = node.left; 
    node.left = node.right; 
    node.right = temp; 
  } 
} 

  
10. doubleTree() Solution (Java)

/** 
 Changes the tree by inserting a duplicate node 
 on each nodes's .left. 
  
  
 So the tree... 
    2 
   / \ 
  1   3 
 Is changed to... 
       2 
      / \ 
     2   3 
    /   / 
   1   3 
  / 
 1 
 Uses a recursive helper to recur over the tree 
 and insert the duplicates. 
*/ 
public void doubleTree() { 
 doubleTree(root); 
} 
private void doubleTree(Node node) { 
  Node oldLeft; 
  if (node == null) return; 
  // do the subtrees 
  doubleTree(node.left); 
  doubleTree(node.right); 
  // duplicate this node to its left 
  oldLeft = node.left; 
  node.left = new Node(node.data); 
  node.left.left = oldLeft; 
} 

  
11. sameTree() Solution (Java)

/* 
 Compares the receiver to another tree to 
 see if they are structurally identical. 
*/ 
public boolean sameTree(BinaryTree other) { 
 return( sameTree(root, other.root) ); 
} 
/** 
 Recursive helper -- recurs down two trees in parallel, 
 checking to see if they are identical. 
*/ 
boolean sameTree(Node a, Node b) { 
  // 1. both empty -> true 
  if (a==null && b==null) return(true); 
  // 2. both non-empty -> compare them 
  else if (a!=null && b!=null) { 
    return( 
      a.data == b.data && 
      sameTree(a.left, b.left) && 
      sameTree(a.right, b.right) 
    ); 
  } 
  // 3. one empty, one not -> false 
  else return(false); 
} 

  
12. countTrees() Solution (Java)

/** 
 For the key values 1...numKeys, how many structurally unique 
 binary search trees are possible that store those keys? 
 Strategy: consider that each value could be the root. 
 Recursively find the size of the left and right subtrees. 
*/ 
public static int countTrees(int numKeys) { 
  if (numKeys <=1) { 
    return(1); 
  } 
  else { 
    // there will be one value at the root, with whatever remains 
    // on the left and right each forming their own subtrees. 
    // Iterate through all the values that could be the root... 
    int sum = 0; 
    int left, right, root; 
    for (root=1; root<=numKeys; root++) { 
      left = countTrees(root-1); 
      right = countTrees(numKeys - root); 
      // number of possible trees with this root == left*right 
      sum += left*right; 
    } 
    return(sum); 
  } 
} 

  
13. isBST1() Solution (Java)

/** 
 Tests if a tree meets the conditions to be a 
 binary search tree (BST). 
*/ 
public boolean isBST() { 
  return(isBST(root)); 
} 
/** 
 Recursive helper -- checks if a tree is a BST 
 using minValue() and maxValue() (not efficient). 
*/ 
private boolean isBST(Node node) { 
  if (node==null) return(true); 
  // do the subtrees contain values that do not 
  // agree with the node? 
  if (node.left!=null && maxValue(node.left) > node.data) return(false); 
  if (node.right!=null && minValue(node.right) <= node.data) return(false); 
  // check that the subtrees themselves are ok 
  return( isBST(node.left) && isBST(node.right) ); 
} 

  
14. isBST2() Solution (Java)

/** 
 Tests if a tree meets the conditions to be a 
 binary search tree (BST). Uses the efficient 
 recursive helper. 
*/ 
public boolean isBST2() { 
 return( isBST2(root, Integer.MIN_VALUE, Integer.MAX_VALUE) ); 
} 
/** 
  Efficient BST helper -- Given a node, and min and max values, 
  recurs down the tree to verify that it is a BST, and that all 
  its nodes are within the min..max range. Works in O(n) time -- 
  visits each node only once. 
*/ 
private boolean isBST2(Node node, int min, int max) { 
  if (node==null) { 
    return(true); 
  } 
  else { 
   // left should be in range  min...node.data 
    boolean leftOk = isBST2(node.left, min, node.data); 
    // if the left is not ok, bail out 
    if (!leftOk) return(false); 
    // right should be in range node.data+1..max 
    boolean rightOk = isBST2(node.right, node.data+1, max); 
    return(rightOk); 
  } 
}