Rather than offer pseudocode for the algorithms, the actual code is presented with heavy commenting. The reader should carefully match what is said below with the description given above. Note that inserting and deleting procedures have to proceed recursively as whatever affects a given level may affect the one above it. Thus, several of the procedures are recursive and return a flag to the level above to inform the calling version of the same (or another) procedure about the necessity of splitting or consolidating. Also observe that subsidiary procedures are included inside their main procedures rather than being allowed to be visible in the main module.
IMPLEMENTATION MODULE BTrees;
(******************
Design by R. Sutcliffe copyright 1995-1996
Initial Code by Gordon Tisher
June 9, 1995; last modified 1999 08 30
Modified and rewritten by R. Sutcliffe 1996 10 10
Bug in rearrange removed 1999 08 30; weren't checking case of no data to right
big thanks to Florenz Plassmann, Münster, Deutschland, who had the wit to try
the test code with an order three tree and uncovered a huge flaw.
also added more and better comments in that section
deanonymized main data structure
and removed a redundant count variable in DelSpecial
This module provides a B-Tree ADT.
******************)
FROM Storage IMPORT
ALLOCATE, DEALLOCATE;
FROM STextIO IMPORT
WriteString, WriteLn, SkipLine;
FROM SWholeIO IMPORT
WriteCard;
FROM DataADT IMPORT
Assign, GetKey, WriteData, ActionProc, Compare, CompareResults;
CONST
maxIndex = 2 * order;
maxIndexPlus = maxIndex + 1;
TYPE
BTree = POINTER TO BNode;
ItemArray = ARRAY[1..maxIndexPlus] OF ItemType;
PointerArray = ARRAY[0..maxIndexPlus] OF BTree;
BNode =
RECORD
numItems : CARDINAL;
state : BTreeState;
Items : ItemArray;
Pointers : PointerArray;
END; (* record *)
(* There is one extra position in the arrays to aid sorting a new item in. This saves a lot of copying to and from temporaries. *)
(* BTreeState = (allRight, empty, entreeFailed) *)
(************************************
Utility Procedures
************************************)
PROCEDURE FindPos (keyToSearchFor : KeyType; node : BTree; VAR pos : CARDINAL);
(* find the position within a node of a data item by search key before or at which the item would go
Pre: node is a valid tree
Post: the position returned is that at or before keyToSearchFor belongs. If the keyToSearchFor is smaller than any of the data, returns 1; if keyToSearchFor is larger than any of the data, returns node^.numItems+1 *)
BEGIN
pos := 1;
WHILE (pos <= node^.numItems)
AND (Compare(keyToSearchFor, GetKey (node^.Items[pos]) ) # less)
DO
INC (pos);
END; (* while *)
END FindPos;
(************************************
Exported Procedures
************************************)
PROCEDURE Status (tree : BTree) : BTreeState;
(* Pre : t is a valid initialized BTree
Post : The State of the tree is returned *)
BEGIN
RETURN tree^.state;
END Status;
PROCEDURE Init (VAR tree : BTree);
(* Allocates memory for a new node and initializes it
Pre: none
Post: if memory is found, sets up the tree structure with NIL pointers and zero items *)
VAR
count: CARDINAL;
temp : BTree;
BEGIN
NEW (temp);
IF (temp # NIL)
THEN
temp^.numItems := 0;
FOR count := 0 TO maxIndexPlus
DO
temp^.Pointers[count] := NIL;
END; (* for *)
temp^.state := allRight;
tree := temp;
END; (* if *)
END Init;
PROCEDURE Destroy (VAR tree : BTree);
(* disposes the whole tree *)
PROCEDURE disp (node : BTree; level : CARDINAL);
(* recursively remove a node *)
VAR
count : CARDINAL;
BEGIN
IF (node # NIL)
THEN
FOR count := 0 TO node^.numItems
DO
disp (node^.Pointers[count], level+1);
END; (* for *)
DISPOSE (node);
END; (* if *)
END disp;
BEGIN
disp (tree, 0);
END Destroy;
PROCEDURE Add (VAR tree : BTree; data : ItemType);
(* Adds a new item to the tree. *)
PROCEDURE Insert (VAR data : ItemType; pos : CARDINAL; node : BTree;
VAR newNode : BTree) : BOOLEAN;
(* put the data item into the specified node position and the newNode pointer after it if one is generated. *)
(* returns true if inserting is finished, false as a flag to the next higher level to insert the new centre item up there after a split. *)
VAR
count : CARDINAL;
temp : BTree;
BEGIN
(* first move things over to make room for new item *)
FOR count := node^.numItems TO pos BY -1
DO
Assign (node^.Items[count], node^.Items[count+1]);
node^.Pointers[count+1] := node^.Pointers[count];
END; (* for *)
(* pop new one into place *)
Assign (data, node^.Items[pos]);
node^.Pointers[pos] := newNode;
(* check to see if the resulting node needs to be split *)
IF (node^.numItems = maxIndex) (* was at max before so split it! *)
THEN
Init (temp); (* make a new node *)
IF (temp # NIL)
THEN (* split node *)
(* reset number of items in each to order *)
node^.numItems := order;
temp^.numItems := order;
(* store new middle for upstairs to insert recursively *)
Assign (node^.Items[order+1], data);
(* copy new zeroth pointer *)
temp^.Pointers[0] := node^.Pointers[order+1];
(* copy data and rest of pointers into both *)
FOR count := 1 TO order
DO (* clean up the rest of the node *)
node^.Pointers[count+order] := NIL;
Assign (node^.Items[count+order+1], temp^.Items[count]);
temp^.Pointers[count] := node^.Pointers[count+order+1];
END; (* for *)
node^.Pointers[maxIndexPlus] := NIL; (* fix last pointer too; not in loop *)
tree^.state := allRight
ELSE (* did not work *)
tree^.state := entreeFailed;
END; (* if temp *)
newNode := temp;
RETURN FALSE; (* flag for split *)
ELSE (* don't split it just adjust count *)
INC (node^.numItems);
newNode := NIL;
RETURN TRUE; (* flag for just did an insert *)
END; (* if node*)
END Insert;
PROCEDURE AddItem (VAR data : ItemType; node : BTree;
VAR newNode : BTree): BOOLEAN;
(* returns true if added with no split, false if added with split *)
VAR
pos : CARDINAL;
BEGIN
(* look for correct position *)
FindPos (GetKey (data), node, pos);
(* insert the item at or to the left of the position found *)
IF (node^.Pointers[pos-1] # NIL) (* there is a node below *)
THEN (* go down there *)
IF ~AddItem (data, node^.Pointers[pos-1], newNode) (* node below was split *)
THEN (* so find spot for dividing item that was passed up here *)
FindPos (GetKey (data), node, pos);
RETURN Insert (data, pos, node, newNode);
ELSE
RETURN TRUE; (* tell level up that no split *)
END; (* if ~AddItem *)
ELSE (* add the item to the current node *)
(* and send back the result of doing that *)
RETURN Insert (data, pos, node, newNode);
END; (* if node *)
END AddItem;
VAR
temp, newNode : BTree;
BEGIN (* main for Add *)
newNode := NIL;
IF ~AddItem (data, tree, newNode) (* got a split on first level below *)
THEN (* so, must turn temp into a new root *)
Init (temp); (* set up a new node for it *)
IF (temp # NIL)
THEN
temp^.numItems := 1; (* it has only this item for now *)
temp^.Pointers[0] := tree;
Assign (data, temp^.Items[1]);
temp^.Pointers[1] := newNode;
tree := temp;
END; (* if temp *)
END; (* if ~AddItem *)
END Add;
PROCEDURE Delete (VAR tree : BTree; key : KeyType);
(* deletes an item whose key is equal to _key_ from the tree
If the item isn't there, nothing happens, but if the tree was empty and we tried to delete the state is set to empty. *)
PROCEDURE Rearrange (node : BTree; pos : CARDINAL) : BOOLEAN;
(* this sub-procedure is called to rearrange a parent node with respect to its children when a deletion causes the number of items to become too small *)
(* pos is that of the data item 1..order in the parent node separating the two child nodes that need combining *)
(* returns true if node needs no further rearrangement above, false if it does *)
VAR
child, sibling : BTree;
count, num : CARDINAL;
BEGIN
child := node^.Pointers[pos-1]; (* look at the child node that's short on data *)
(* check to see if we must combine with sibling having lesser data to its left *)
IF (* first case *) (node^.Pointers[pos] = NIL) (* no node available to the right *)
OR (* second case *) ((pos > 1) (* there is a sibling to the left *)
AND (node^.Pointers[pos]^.numItems = order))
(* no surplus among the greater to the right *)
(* The 'default' situation is that there is a node to the right and it can be used,
else we stay here *)
THEN (* must stay here and combine with node of the lesser data *)
DEC (pos);
sibling := node^.Pointers[pos-1]; (* node from the lesser data position *)
(* calculate num to move sibling ==> child *)
num := (sibling^.numItems + 1 - order) DIV 2;
IF (num > 0)
THEN (* move num items from sibling ==> child *)
FOR count := (order-1) TO 1 BY -1 (* shift right to make room *)
DO
Assign (child^.Items[count], child^.Items[count+num]);
child^.Pointers[count+num] := child^.Pointers[count];
END; (* for count *)
(* move old separator down to child *)
Assign (node^.Items[pos], child^.Items[num]);
child^.Pointers[num] := child^.Pointers[0];
(* now move stuff over *)
FOR count := (num-1) TO 1 BY -1 (* copy from adjacent node *)
DO
Assign (sibling^.Items[count+(sibling^.numItems+1-num)],
child^.Items[count]);
child^.Pointers[count] :=
sibling^.Pointers[count+(sibling^.numItems+1-num)];
sibling^.Pointers[count+(sibling^.numItems+1-num)] := NIL;
END; (* for count *)
child^.Pointers[0] := sibling^.Pointers[sibling^.numItems+1-num];
(* move last item in node with extras up to be new separator *)
Assign (sibling^.Items[sibling^.numItems+1-num], node^.Items[pos]);
node^.Pointers[pos] := child;
(* adjust item numbers in both nodes *)
sibling^.numItems := sibling^.numItems - num;
child^.numItems := order - 1 + num;
(* adjust last pointer in sibling node *)
sibling^.Pointers[sibling^.numItems+1] := NIL;
RETURN TRUE; (* tell upstairs all OK *)
ELSE (* none avail to move, so just merge nodes *)
Assign (node^.Items[pos], sibling^.Items[sibling^.numItems + 1]);
sibling^.Pointers[sibling^.numItems + 1] := child^.Pointers[0];
FOR count := 1 TO (order-1) (* copy child to sibling *)
DO
Assign (child^.Items[count], sibling^.Items[count+sibling^.numItems+1]);
sibling^.Pointers[count+sibling^.numItems+1] := child^.Pointers[count];
END; (* for count *)
(* shift left node items *)
FOR count := pos TO (node^.numItems - 1)
DO
Assign (node^.Items[count+1], node^.Items[count]);
node^.Pointers[count] := node^.Pointers[count+1];
END; (* for count *)
sibling^.numItems := maxIndex; (* adjust num of items to max *)
node^.Pointers[node^.numItems] := NIL; (* get rid of pointer *)
DEC (node^.numItems);
DISPOSE (child);
RETURN (node^.numItems >= order); (* flag up if consolidation needed *)
END; (* if num *)
(* this section combines our child node with a sibling on its right *)
(* We get here always if the child is the first node, or, in the default, if there
is a node to the right of our problem child and it has a surplus available *)
ELSE
sibling := node^.Pointers[pos];
(* the one after or having greater data, that is, to the child's right *)
num := (sibling^.numItems - order + 1) DIV 2;(* calculate num to move *)
(* copy item from parent to orderth position first *)
Assign (node^.Items[pos], child^.Items[order]);
child^.Pointers[order] := sibling^.Pointers[0];
IF (num > 0)
THEN (* move items from sibling to this child in next positions *)
FOR count := 1 TO (num-1)
DO
Assign (sibling^.Items[count], child^.Items[count+order]);
child^.Pointers[count+order] := sibling^.Pointers[count]
END; (* for count *)
(* new separator mode from sibling *)
Assign (sibling^.Items[num], node^.Items[pos]);
(* now, fix sibling up *)
sibling^.Pointers[0] := sibling^.Pointers[num];
DEC (sibling^.numItems, num);
(* shift left remaining elements of that sibling *)
FOR count := 1 TO sibling^.numItems
DO
Assign (sibling^.Items[count+num], sibling^.Items[count]);
sibling^.Pointers[count] := sibling^.Pointers[count+num];
sibling^.Pointers[count+num] := NIL;
END; (* for count *)
child^.numItems := order - 1 + num;
RETURN TRUE;
ELSE (* not enough on that side so merge nodes *)
FOR count := 1 TO order
DO
Assign (sibling^.Items[count], child^.Items[count+order]);
child^.Pointers[count+order] := sibling^.Pointers[count];
END; (* for count *)
(* shift left node items *)
FOR count := pos TO (node^.numItems - 1)
DO
Assign (node^.Items[count+1], node^.Items[count]);
node^.Pointers[count] := node^.Pointers[count+1];
END; (* for *)
child^.numItems := maxIndex; (* adjust num of items to max *)
node^.Pointers[node^.numItems] := NIL; (* get rid of pointer *)
DEC (node^.numItems);
DISPOSE (sibling);
RETURN (node^.numItems >= order);
END; (* if num *)
END; (* if pos *)
END Rearrange;
PROCEDURE DelSpecial (node : BTree; VAR data : ItemType) : BOOLEAN;
(* after deleting from an interior node, find largest item less than it to remove from a node below and pass it up in "data" to become the new dividor *)
(* returns true if node is OK, false if too small & needs work from above *)
BEGIN
(* check for more nodes and do it recursively to the greater side to get the biggest *)
IF (node^.Pointers[node^.numItems] # NIL)
THEN
(* see if level below says rearrange needed *)
IF ~DelSpecial (node^.Pointers[node^.numItems], data)
THEN (* so, do it *)
RETURN Rearrange (node, node^.numItems+1);
ELSE
RETURN TRUE;
END; (* if *)
ELSE (* remove the item *)
Assign (node^.Items[node^.numItems], data); (* save in data to send up top *)
DEC (node^.numItems); (* decrease this node size *)
RETURN (node^.numItems >= order); (* and return fla to next level up *)
END; (* if *)
END DelSpecial;
PROCEDURE Del (node : BTree; key : KeyType) : BOOLEAN;
(* finds and delete the item with the key from the node; works recursively down
returns true if node is OK now, false if next higher level must work on it as too small *)
VAR
count, pos : CARDINAL;
data : ItemType;
BEGIN
FindPos (key, node, pos); (* key is at or left of position *)
IF (pos > 1) AND (pos <= node^.numItems)
(* else, left of 1 or right of numItems means not in this node *)
AND (Compare (GetKey (node^.Items[pos-1]),key) = equal) (* check to see if bang on *)
THEN (* item actually found in this node *)
DEC (pos); (* now at the item to delete *)
IF (node^.Pointers[pos-1] # NIL) (* stuff hanging below it & prior to it *)
THEN (* use prior pointer to fish below for largest item for possible promotion *)
(* see if got it with rearranging needed *)
IF ~DelSpecial (node^.Pointers[pos-1], data)
THEN (* do a rearrange as node below has too few items *)
Assign (data, node^.Items[pos]); (* so put it in place *)
RETURN Rearrange (node, pos); (* and do the rearrange on this parent *)
ELSE (* no rearrange, so just replace item with one from lower down *)
Assign (data, node^.Items[pos]);
RETURN TRUE; (* and tell upstairs we're happy *)
END; (* if *)
ELSE (* nothing below so node of found item is a leaf *)
FOR count := pos TO (node^.numItems-1)
DO (* move everything over to the left *)
Assign (node^.Items[count+1], node^.Items[count]);
(* don't need to assign pointers, as the node is a leaf *)
END; (* for *)
DEC (node^.numItems);
RETURN (node^.numItems >= order); (* tell upstairs if rearrange needed *)
END; (* if *)
ELSE
(* item is not in this node so try down below using pointer left of node position# *)
IF (node^.Pointers[pos-1] # NIL) (* there is a "below" before it *)
AND ~Del (node^.Pointers[pos-1], key) (* and we need to rearrange *)
THEN
RETURN Rearrange (node, pos);
(* rearrange this node; provide position in parent to the left of which lies the
node (pointer one less) below that has declined in population and send flag up *)
ELSE
RETURN TRUE; (* tell upstairs no rearrange *)
END; (* if node *)
END; (* if pos *)
END Del;
VAR
oldTree : BTree;
BEGIN (* main delete proc *)
IF tree^.numItems = 0 (* nothing to delete *)
THEN (* this is an error; set flag so client can find out if it checks *)
tree^.state := empty;
END;
IF ~Del (tree, key) AND (tree^.numItems = 0) (* after del *)
AND (tree^.Pointers[0] # NIL)
THEN
oldTree := tree;
tree := oldTree^.Pointers[0];
DISPOSE (oldTree);
tree^.state := allRight;
END; (* if *)
END Delete;
PROCEDURE Depth (tree : BTree) : CARDINAL;
(* returns the number of levels in the tree *)
BEGIN
IF (tree # NIL)
THEN
RETURN Depth (tree^.Pointers[0]) + 1;
ELSE
RETURN 0;
END; (* if *)
END Depth;
PROCEDURE Search (tree : BTree; key : KeyType; VAR data : ItemType) : BOOLEAN;
(* if found, returns TRUE and _data_ returns item at that point *)
VAR
pos : CARDINAL;
BEGIN
IF (tree = NIL)
THEN
RETURN FALSE;
ELSE
FindPos (key, tree, pos);
IF (pos > 1) AND (pos <= maxIndexPlus)
AND (Compare (GetKey (tree^.Items[pos-1]), key) = equal)
THEN
Assign (tree^.Items[pos-1], data);
RETURN TRUE;
ELSE
RETURN Search (tree^.Pointers[pos-1], key, data);
END; (* if pos *)
END; (* if tree *)
END Search;
PROCEDURE WriteTree (tree : BTree);
(* writes out the tree *)
PROCEDURE WriteInOrder (node : BTree);
VAR
count : CARDINAL;
BEGIN
IF (node = NIL)
THEN
RETURN;
END; (* if *)
WriteInOrder (node^.Pointers[0]);
FOR count := 1 TO node^.numItems
DO
WriteData (node^.Items[count]);
INC (gcount);
WriteString (", ");
IF (gcount > 10)
THEN
WriteLn;
gcount := 1;
END; (* if *)
WriteInOrder (node^.Pointers[count]);
END; (* for *)
END WriteInOrder;
PROCEDURE WriteNodes (node : BTree; level : CARDINAL);
VAR
count : CARDINAL;
BEGIN
IF (node = NIL)
THEN
RETURN;
END; (* if *)
FOR count := 1 TO (level*2)
DO
WriteString (" ");
END; (* for *)
IF node^.numItems > 0
THEN
WriteData (node^.Items[1]);
END; (* if *)
FOR count := 2 TO node^.numItems
DO
WriteString (", ");
WriteData (node^.Items[count]);
END; (* for *)
WriteLn;
INC (gcount);
IF (gcount > 33)
THEN
WriteString ("press return to continiue...");
SkipLine;
gcount := 1;
END; (* if *)
FOR count := 0 TO maxIndex
DO
WriteNodes (node^.Pointers[count], level+1);
END; (* for *)
END WriteNodes;
VAR
gcount : CARDINAL;
BEGIN
WriteString ("*************"); WriteLn;
WriteString ("Tree view:"); WriteLn;
gcount := 1;
WriteNodes (tree, 0);
WriteLn;
IF gcount > 34
THEN
WriteString ("press return to continue...");
SkipLine;
END; (* if *)
WriteString ("Inorder view:"); WriteLn;
gcount := 1;
WriteInOrder (tree);
WriteLn;
WriteString ("*************"); WriteLn;
END WriteTree;
PROCEDURE Traverse (tree : BTree; Proc : ActionProc);
(* Pre : tree is a valid initialized BTree
Post : the nodes are traversed inorder and Proc is performed on each data item. *)
VAR
count : CARDINAL;
BEGIN
IF (tree = NIL)
THEN
RETURN;
END; (* if *)
Traverse (tree^.Pointers[0], Proc);
FOR count := 1 TO tree^.numItems
DO
Proc (tree^.Items[count]);
Traverse (tree^.Pointers[count], Proc);
END; (* for count *)
END Traverse;
END BTrees.
This module was given a brief workout using cardinals as the data type, and their own value as the key. Observe that the data type to be entered could have been a complex record as long as some compare procedure was defined on a key field. First, the data type to be imported and entreed is defined:
DEFINITION MODULE DataADT;
TYPE
CompareResults = (less, equal, greater);
KeyFieldType = CARDINAL;
DataType = CARDINAL;
ActionProc = PROCEDURE (DataType);
PROCEDURE Assign (a : DataType; VAR b : DataType);
PROCEDURE GetKey (a : DataType) : KeyFieldType;
PROCEDURE WriteData (a : DataType);
PROCEDURE Compare (a, b : KeyFieldType) : CompareResults;
END DataADT.
IMPLEMENTATION MODULE DataADT;
IMPORT SWholeIO;
PROCEDURE Assign (a : DataType; VAR b : DataType);BEGIN
b:= a;
END Assign;
PROCEDURE GetKey (a : DataType) : KeyFieldType;
BEGIN
RETURN a;
END GetKey;
PROCEDURE WriteData (a : DataType);
BEGIN
SWholeIO.WriteCard (a,0);
END WriteData;
PROCEDURE Compare (a, b : KeyFieldType) : CompareResults;
BEGIN
IF a = b
THEN
RETURN equal
ELSIF a < b THEN
RETURN less
ELSE
RETURN greater
END
END Compare;
END DataADT.
The actual test uses the same data as in the initial discussion. A few additional insertions (same value as one already there) and deletions (a value not present) are also done. At intervals, the tree is printed out, and at one point, a traverse is done adding all the key values.
MODULE TestBTrees;
(* A simple program to test the Binary tree library module.
by R. Sutcliffe
last modified 1996 10 15 *)
IMPORT BTrees, DataADT, SWholeIO, STextIO;
VAR
theTree : BTrees.BTree;
sum : CARDINAL;
PROCEDURE Summit (item : DataADT.DataType);
BEGIN
sum := sum + DataADT.GetKey (item)
END Summit;
BEGIN
BTrees.Init (theTree);
BTrees.Add (theTree, 15);
BTrees.Add (theTree, 4);
BTrees.Add (theTree, 6);
BTrees.Add (theTree, 12);
BTrees.WriteTree(theTree);
BTrees.Add (theTree, 11);
BTrees.WriteTree(theTree);
BTrees.Add (theTree, 17);
BTrees.Add (theTree, 20);
BTrees.Add (theTree, 30);
BTrees.Add (theTree, 31);
BTrees.Add (theTree, 5);
BTrees.Add (theTree, 16);
BTrees.Add (theTree, 37);
BTrees.WriteTree(theTree);
sum := 0;
BTrees.Traverse (theTree, Summit);
STextIO.WriteLn;
STextIO.WriteString ("Sum is ");
SWholeIO.WriteCard (sum, 10);
STextIO.WriteLn;
BTrees.Delete (theTree, 15);
BTrees.WriteTree(theTree);
BTrees.Delete (theTree, 16);
BTrees.WriteTree(theTree);
BTrees.Delete (theTree, 37);
BTrees.Delete (theTree, 12);
BTrees.WriteTree(theTree);
BTrees.Delete (theTree, 17);
BTrees.WriteTree(theTree);
BTrees.Delete (theTree, 42);
BTrees.WriteTree(theTree);
BTrees.Add (theTree, 4);
BTrees.WriteTree(theTree);
END TestBTrees.
When this program was run, the output looked like this:
************* Tree view: 4, 6, 12, 15 Inorder view: 4, 6, 12, 15, ************* ************* Tree view: 11 4, 6 12, 15 Inorder view: 4, 6, 11, 12, 15, ************* ************* Tree view: 11, 17 4, 5, 6 12, 15, 16 20, 30, 31, 37 Inorder view: 4, 5, 6, 11, 12, 15, 16, 17, 20, 30, 31, 37, ************* Sum is 204 ************* Tree view: 11, 17 4, 5, 6 12, 16 20, 30, 31, 37 Inorder view: 4, 5, 6, 11, 12, 16, 17, 20, 30, 31, 37, ************* ************* Tree view: 11, 20 4, 5, 6 12, 17 30, 31, 37 Inorder view: 4, 5, 6, 11, 12, 17, 20, 30, 31, 37, ************* ************* Tree view: 6, 20 4, 5 11, 17 30, 31 Inorder view: 4, 5, 6, 11, 17, 20, 30, 31, ************* ************* Tree view: 20 4, 5, 6, 11 30, 31 Inorder view: 4, 5, 6, 11, 20, 30, 31, ************* ************* Tree view: 20 4, 5, 6, 11 30, 31 Inorder view: 4, 5, 6, 11, 20, 30, 31, ************* ************* Tree view: 5, 20 4, 4 6, 11 30, 31 Inorder view: 4, 4, 5, 6, 11, 20, 30, 31, *************