CS 131 LECTURE 11 - BINARY TREES

Terminology:

Binary Tree: An Empty Tree Or A Tree Whose Left And Right Subtrees Are Binary Trees

Parent: Node Directly Above Any Given Node

Left And Right Child: Node Directly Below To The Left Or Directly Below To The Right

Root Node: Single Node Of A Binary Tree That Has No Parent

Leaf Node: Any Node Of A Binary Tree That Has No Children

Level: The Root Is At Level 1, Every Other Node Is At A Level One Greater Than Its Parent

Depth Or Height: The Maximum Level Of All Nodes Of The Binary Tree

Binary Tree Package Specification

GENERIC
  TYPE Elements IS PRIVATE;
  WITH PROCEDURE Put(Item: IN Elements)
    IS <>;
PACKAGE Binary_Tree_Package IS
  TYPE Nodes;
  TYPE Trees IS ACCESS Nodes;
  TYPE Nodes IS
    RECORD
      Left: Trees;
      Data: Elements;
      Right: Trees;
    END RECORD;
  PROCEDURE Preorder (Root: IN Trees);
  PROCEDURE Inorder (Root: IN Trees);
  PROCEDURE Postorder (Root: IN Trees);
END Binary_Tree_Package;

Important Points:

1. The Representation For Binary Trees Is Intentionally Not Hidden

2. This Package Is Intended To Form The Basis Of Other Packages That Implement Abstract Data Types

Binary Tree Package Body

PACKAGE BODY Binary_Tree_Package IS
  PROCEDURE Preorder (Root: IN Trees) IS
  BEGIN
    IF Root /= NULL THEN
      Put(Root.Data);
      Preorder(Root.Left);
      Preorder(Root.Right);
    END IF;
  END Preorder;
  PROCEDURE Inorder (Root: IN Trees) IS
  BEGIN
    IF Root /= NULL THEN
      Inorder(Root.Left);
      Put(Root.Data);
      Inorder(Root.Right);
    END IF;
  END Inorder;
  PROCEDURE Postorder (Root: IN Trees) IS
  BEGIN
    IF Root /= NULL THEN
      Postorder(Root.Left);
      Postorder(Root.Right);
      Put(Root.Data);
    END IF;
  END Postorder;
END Binary_Tree_Package;

Arithmetic Expression As Binary Tree

Basic Three Tree Traversals

Terminology:

Binary Search Tree: An Empty Binary Tree Or A Binary Tree With The Following Properties:
1. All The Key Fields In The Left Subtree Are Less The Root Key

2. All Key Fields In The Right Subtree Are Greater Than The Root Key

3. Both Subtrees Are Binary Search Trees

Binary Search Tree With Integer Keys

Binary Search Tree Package Specification

WITH Binary_Tree_Package;
GENERIC
  TYPE Elements IS PRIVATE;
  TYPE Keys IS PRIVATE;
  WITH FUNCTION ">"(Left,Right: Keys) RETURN
    Boolean IS <>;
  WITH PROCEDURE Put(Item: Elements) IS <>;
  WITH FUNCTION Get_Key(Element: Elements)
    RETURN Keys;
PACKAGE Binary_Search_Tree_Package IS
  TYPE Trees IS PRIVATE;
  PROCEDURE Insert(Tree: IN OUT Trees;
    Element: IN Elements);
  PROCEDURE Delete(Tree: IN OUT Trees;
    Key: IN Keys);
  PROCEDURE Find(Tree: IN OUT Trees;
    Key: IN Keys; Element: OUT Elements;
    Found: OUT Boolean);
  PROCEDURE Put(Tree: IN Trees);
  Full_Tree,Duplicate_Key: EXCEPTION;
PRIVATE
  PACKAGE BT IS NEW Binary_Tree_Package
   (Elements);
  TYPE Trees IS NEW BT.Trees;
END Binary_Search_Tree_Package;
 

Binary Search Tree Package Body

WITH Unchecked_Deallocation;
PACKAGE BODY Binary_Search_Tree_Package IS
  PROCEDURE Deallocate_Node IS NEW
  Unchecked_Deallocation(BT.Nodes,BT.Trees);
  PROCEDURE Search(Tree: IN Trees;
    Key: IN Keys; Current,Parent: OUT Trees;
    Found: OUT Boolean) IS SEPARATE;
  PROCEDURE Insert(Tree: IN OUT Trees;
    Element: IN Elements) IS SEPARATE;
  PROCEDURE Delete(Tree: IN OUT Trees;
    Key: IN Keys) IS SEPARATE;
  PROCEDURE Find(Tree: IN OUT Trees;
    Key: IN Keys; Element: OUT Elements;
    Found: OUT Boolean) IS
    Parent,Current: Trees;
    In_List: Boolean;
  BEGIN
    Search(Tree,Key,Parent,Current,In_List);
    IF In_List THEN
      Element := Current.Data;
    END IF;
    Found := In_List;
  END Find;
  PROCEDURE Put(Tree: IN Trees) IS
  BEGIN BT.Inorder(BT.Trees(Tree)); END Put;
END Binary_Search_Tree_Package;

Search Procedure

SEPARATE (Binary_Search_Tree_Package)
PROCEDURE Search(Tree: IN Trees;
  Key: IN Keys; Current,Parent: OUT Trees;
  Found: OUT Boolean) IS
  Last: Trees := NULL;
  This: Trees := Tree;
BEGIN
  WHILE This /= NULL LOOP
    EXIT WHEN Key = Get_Key(This.Data);
    Last := This;
    IF Key > Get_Key(This.Data) THEN
      This := Trees(This.Right);
    ELSE
      This := Trees(This.Left);
    END IF;
  END LOOP;
  Found := This /= NULL AND THEN
    Key = Get_Key(This.Data);
  Parent := Last;
  Current := This;
END Search;

Important Point:

1. The Efficiency Of The Search Procedure Is O(log2n) Provided The Tree Is Sufficiently Balanced

Insert Procedure

SEPARATE (Binary_Search_Tree_Package)
PROCEDURE Insert(Tree: IN OUT Trees;
  Element: IN Elements) IS
  Key: Keys := Get_Key(Element);
  BT_Leaf: BT.Trees;
  Leaf,Current,Parent: Trees;
  Found: Boolean;
BEGIN
  Search(Tree,Key,Current,Parent,Found);
  IF Found THEN
    RAISE Duplicate_Key;
  END IF;
  BT_Leaf := NEW BT.Nodes;
  Leaf := Trees(BT_Leaf);
  Leaf := (NULL, Element, NULL);
  IF Parent = NULL THEN
    Tree := Leaf;
  ELSIF Key > Get_Key(Parent.Data) THEN
    Parent.Right := BT.Trees(Leaf);
  ELSE
    Parent.Left := BT.Trees(Leaf);
  END IF;
EXCEPTION
  WHEN Storage_Error =>
    RAISE Full_Tree;
END Insert;

Major Issue:

1. Deletion Is The Most Complicated Operation, It Is Best To Consider Three Cases:
a) Left Node: Make Parent's Pointer To It Null

b) One Child: Make Parent Point To The Corresponding Grandchild

c) Two Children: Delete Its Inorder Predecessor And Copy The Predecessor's Value Into The Node

Delete Procedure

SEPARATE (Binary_Search_Tree_Package)
PROCEDURE Delete(Tree: IN OUT Trees;
  Key: IN Keys) IS
  Current,Parent: Trees;
  Found: Boolean;
  PROCEDURE Delete_Node(Node: IN OUT Trees)
    IS SEPARATE;
BEGIN
  Search(Tree,Key,Current,Parent,Found);
  IF Found THEN
    IF Current = Tree THEN
      Delete_Node(Tree);
    ELSIF Trees(Parent.Left) = Current THEN
      Delete_Node(Trees(Parent.Left));
    ELSE
      Delete_Node(Trees(Parent.Right));
    END IF;
  END IF;
END Delete;

Important Point:

1. Delete Node Is Passed A Pointer To The Node To Be Deleted

Delete Node Procedure

SEPARATE (Binary_Search_Tree_Package.Delete)
PROCEDURE Delete_Node(Node: IN OUT Trees) IS
  Max,Par: Trees; Remove: BT.Trees;  
BEGIN
  Remove := BT.Trees(Node);
  IF BT."="(Node.Right,NULL) THEN
    Node := Trees(Node.Left); -- 0-1 Child
  ELSIF BT."="(Node.Left,NULL) THEN
    Node := Trees(Node.Right); -- 1 Child
  ELSE -- 2 Children
    Par := Trees(Node.Left);
    Max := Trees(Par.Right)
    IF Max = NULL THEN
      Node.Left := Trees(Par.Left);
      Node.Data := Par.Data;
      Remove := BT.Trees(Par);
    ELSE
      WHILE BT."/="(Max.Right,NULL) LOOP
        Par := Max; Max := Trees(Max.Right);
      END LOOP;
      Par.Right := Max.Left;
      Node.Data := Max.Data;
      Remove := BT.Trees(Max);
    END IF;
  END IF;
  Deallocate_Node(Remove);
END Delete_Node;