Revision: Elementary Data Structures and Associated Algorithms, Basic Input/Output Computer Science (Theory) ISC (Commerce) Class 11 CISCE

A node that has no child nodes is called a leaf node. Such nodes have a degree of zero. In the given figure, nodes D, G, K, M are leaf nodes. Leaf nodes are also known as terminal nodes.

Data items which are not divided into sub-items are called as elementary
items.

Depth of a tree is defined as maximum level of any nodes in the tree. If root is level 0 then depth or height of tree is equal to 1 + largest level number. 

For eg: Depth of above tree is 5.

A node that does not have a parent is called the root node. Generally, the first node of a tree is considered the root. In the given figure, node A is the root of the tree.

An entity is something that has certain attributes or properties which may be assigned values.

The values themselves may be numeric or non-numeric.

An entity is a real world object, person, concept or a thing about which data can be stored and managed in database.

A data element that is composed of one or more subordinate, smaller data items.

Algorithm: Binary Search
Binary(DATA, LB, UB, ITEM, LOC)
Step 1: Initialize
        BEG = LB
        END = UB
        MID = INT((BEG + END) / 2)
Step 2: While BEG ≤ END AND DATA[MID] ≠ ITEM
            If ITEM < DATA[MID] then
                END = MID - 1
            Else
                BEG = MID + 1
            End If
            MID = INT((BEG + END) / 2)
        End While
Step 3: If DATA[MID] = ITEM then
            LOC = MID
        Else
            LOC = NULL
        End If
Step 4: Exit

Example:

Given a sorted array:

11 22 30 33 40 44 55 60 66 77 80 88 99

ITEM = 40

LB = 1, UB = 13

BEG = 1, END = 13
MID = INT((1+13)/2) = 7 → DATA[7] = 55

40 < 55 → END = 6
MID = INT((1+6)/2) = 3 → DATA[3] = 30

40 > 30 → BEG = 4
MID = INT((4+6)/2) = 5 → DATA[5] = 40

ITEM found at location 5.