BST Per Wolde 2002.05.02 =============== A D T ================ Binary Search Tree ----------------------------------------- add(Object) ----------------------------------------- find(Object) ----------------------------------------- remove(Object) ----------------------------------------- balTree() ----------------------------------------- countNode() ----------------------------------------- getMinValue() ----------------------------------------- print() - preOrder - postOrder - inOrder ----------------------------------------- ==== The basic idea ==== Data by the type Object, are placed in nodes. Theese nodes are linked together into a tree that is the main structure for the container. In this example I let the node be a class of its own inside the tree. Same with the balancingarray, cause it's simplifyed the access and made it more easier to make the balancing algorithm run inside the tree class. The node: +---------------+ | O B J E C T | +-------+-------+ | LEFT | RIGHT | +-------+-------+ | | ! ! : : . . private class Node { public Node(Object o){ this.value = o; this.left = null; this.right = null; } Object value; Node left; Node right; } Array: +-+-+-+-+-+ | | | | | | +-+-+-+-+-+ | ! : . midPos class arr { public arr(int len){ this.elements = 0; this.len = len; this.o = new Object[len]; } private Object[] o; private int len; private int elements; + metoder som: push getObject hasMore getMiddle getMidPos size } ========= A L G O R I T M E R ========== +----------+ | insert | +----------+ ADD(Object): void IF root is null THEN root <- new Node(Object) ELSE INSERT(root,Object) INSERT(Node,Object): void {recursion} IF Object < Node THEN IF Left is null THEN Left <- new Node(Object) ELSE INSERT(Left,Object) ELSE IF Right is null THEN Right <- new Node(Object) ELSE INSERT(Right,Object) +-----------+ | find node | +-----------+ FIND(Object): boolean IF SEARCH(root,Object) NOT null THEN return true ELSE return false -------------- SEARCH(Node,Object): Node {recursion} vars: Node p IF Node NOT null THEN IF Node < Object THEN p <- SEARCH(Left,Object) IF Node > Object THEN p <- SEARCH(Right,Object) IF Node is equal to Object THEN return Node ELSE IF p NOT null AND parent is null THEN parent <- Node return p ---------------------- +----------------+ | remove node | +----------------+ REMOVE(Object): boolean vars: Node p IF FIND(Object) is true THEN p <- SEARCH(root,Object) { IF leaf } IF p.left AND p.right is null THEN IF parent.right is equal to p THEN parent.right <- null ELSE parent.left <- null ELSE root <- null { IF child at right } IF p.left is null AND p.right is NOT null THEN IF parent is null THEN root <- p.right ELSE IF parent.right is equal to p THEN parent.right <- p.right IF parent.left is equal to p THEN parent.left <- p.right { IF child at left } IF p.right is null AND p.left is NOT null THEN IF parent is null THEN root <- p.left ELSE IF parent.right is equal to p THEN parent.right <- p.left IF parent.left is equal to p THEN parent.left <- p.left { IF child at left and right } ELSE IF p.right NOT null AND p.left NOT null THEN REMOVE(p.right,p) -------------------- REMOVE(Node2,Node1): void {recursion} IF Node2.left NOT null THEN while Node2.left.left NOT null DO Node2 <- Node2.left Node1.value <- Node2.left.value Node2.left <- null ELSE Node1.value <- Node1.right.value IF Node1.right.right NOT null Node1.right <- Node1.right.right ELSE Node1.right <- null ------------------ +------------------+ | Balance the tree | +------------------+ BALTREE(): void arr treeArray <- |sorted by value tree| delete tree BALTREE(arr) ------------------ BALTREE(arr): void {recursion} IF arr.size > 0 THEN IF arr getMiddle NOT null THEN add(arr.getMiddle) arr newArray1 = new arr(arr.getMidPos) arr newArray2 = new arr(arr.getMidPos) FOR zero TO arr.getMidPos newArr1.push(arr.getObject) FOR arr.getMidPos TO arr.hasMore newArr2.push(arr.getObject) BALTREE(newArr1) BALTREE(newArr2) ------------------- +-------------+ | Count nodes | +-------------+ COUNTNODE(): int level <- zero deep <- zero return COUNTNODE(root,0) -------------------- COUNTNODE(Node,I): int {recursion} IF Node NOT null THEN IF deep < level THEN deep <- level level increase one I increase one I <- COUNTNODE(Node.left,I) I <- COUNTNODE(Node.right,I) level decrease one return I -------------------- +---------------------------+ | smallest theoretical deep | +---------------------------+ GETMINVALUE(): int return 2 * (LOG(COUNTNODES()+1)-1 -------------------- +-----------------+ | print postOrder | +-----------------+ PRINTPOSTORDER(): void PRINTPOSTORDER(root) -------------------- PRINTPOSTORDER(Node): void {recursion} IF Node NOT null THEN PRINTPOSTORDER(Node.left) PRINTPOSTORDER(Node.right) printout Node -------------------- +----------------+ | print preOrder | +----------------+ PRINTPREORDER(): void PRINTPREORDER(root): void -------------------- PRINTPREORDER(Node): void {recursion} IF Node NOT null THEN printout Node PRINTPREORDER(Node.left) PRINTPREORDER(Node.right) -------------------- +---------------+ | print inOrder | +---------------+ PRINTINORDER(): void PRINTINORDER(root) -------------------- PRINTINORDER(Node):void {recursion} IF Node NOT null THEN PRINTINORDER(Node.left) printout Node PRINTINORDER(Node.right) --------------------