Browse Prior Art Database

Binary Tree Data Structure

IP.com Disclosure Number: IPCOM000080124D
Original Publication Date: 1973-Jan-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Conner, WM: AUTHOR

Abstract

A data set is constructed in the form of a 2-log binary tree. This may be defined as a binary tree in which, in all paths from the null nodes to the root the maximum null height is the same, and in each of these paths not more than two nodes have equal null heights.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 68% of the total text.

Page 1 of 1

Binary Tree Data Structure

A data set is constructed in the form of a 2-log binary tree. This may be defined as a binary tree in which, in all paths from the null nodes to the root the maximum null height is the same, and in each of these paths not more than two nodes have equal null heights.

To insert a record into the tree, the record definition data of records in the path from the root to the new node are placed in a stack. The node of null height zero closest to the root is then selected from the stack, and if this is linked to another node of the same null height, these two nodes and the new node are redefined as a triple subtree with the new node as its root. Using the same stack, this operation is repeated for ascending null heights until a node, which is not linked to a further node at the same null height is detected. If this last detected node is not the root of the tree, the root of the last redefined triple and the node in the stack having the next higher null height are linked at this higher null height.

To delete a record from the tree, the record definition data of records in the path from the root to the record to be deleted are placed in a stack. If this record is not at zero null height, its position is exchanged with a zero null height record either immediately preceding or succeeding it in postorder, and the stack is reformed. The node of null height which is closest to the root is then selected from the stack. If this is the root of a triple,...