263.Write short notes on the following:
(i) Threaded binary tree.
(ii) Buddy systems.
(iii) B - trees.
(iv) Minimum spanning tree. 

Ans:
(i) Threaded binary tree : Consider the linked representation of a binary tree 'T.
Approximately half of the entries is the pointer fields 'LEFT' and 'RIGHT' will
contain null elements. This space may be more efficiently used by replacing the null
entries by some other type of information. Specially we will replace certain null
entries by special pointers which points to nodes in the tree. These special pointers 4
are called 'threads' and binary trees with such pointers are called 'threaded trees'.
There are two major types of threading: - one way threading and two way threading.
In the one way threading of T, a thread will appear in the right field of a node and
will point to the next node in the inorder traversal of T and in the two way threading
of T, a thread will also appear in tl left field of a node and will point to the preceding
node in the inorder traversal of T. There is another kind of one way threading which
corresponds to the preorder traversal of T.
(ii) Buddy systems: A method of handling the storage management problem is kept
separate free lists for blocks of different sizes. Each list contains free blocks of only
one specific size. For example, memory contains 1024 words then it might be
divided into fifteen blocks, one block of 256 words, t blocks of 128 words, four
blocks of 64 words, and 8 blocks of 32 words. Whenever sport is requested the
smallest block is whose size is greater than or equal to the size needed to reserve for
example a block of 97 words is field by a block of size of 128 but in this method
there are several limitation, first, space is wasted due to internal fragmentation,
second, a request of block size 300 cannot be filled. The largest size is maintained is
256, the source of this problem is that free space are never combined
A variation to this scheme is buddy system and is quite useful. In Buddy systems
several free list constituets of various sized blocks are maintained. Adjacent free
blocks are smaller size may be removed from list combined into free blocks of larger
size, and placed on the larger size free list. These larger blocks can be used intact to
satisfy a request for a large amount of memory or they can be split once into their
smallest constituents to satisfy several smaller request.

B-tree : A B-tree is a balanced m-way tree. A node of the tree may contain
many records or key and pointers to children. It is also known as the balanced
sort tree. It finds its use in external sorting. It is not a binary tree.
B-tree of order m has following properties:
(1) each node has a maximum of m children and minimum of m/2 children or
any number from 2 to maximum.
(2) The no. of keys in a node is one less than its no of children. The
arrangement
PO KI PI .... Kn Pn
  
To TI Tn each Tl is a m-way tree
(3) The keys 'in a node Ki — Kn are arranged in sorted order K1 < K2 — <Kn.
All the keys present in the subtree pointed to by a pointer Pi Ki.Pi.Ki+1 are
greater than
(4) When a new key is to be inserted into a full node, the key is split into two
nodes and the key with the median value is inserted in the parent node. In case
the parent node is a root, a new root is created.
(5) All the leaves are on the same level i.e. there is no empty subtree above the level
of the leaves. All the normal nodes of B-tree (Except 'root' and terminal nodes)