(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.
(iii) 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 sub tree 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 sub tree above the level of the leaves. All the normal nodes of B-tree (Except 'root' and terminal nodes) have between m/2 and m children.
(iv) Minimum Spanning Tree : Given a weighted graph G, it is often desired to create a spanning tree T for G, such that the sum of weights of the edges in T is the least. Such a tree is called a minimum spanning tree and represents the cheapest way of connecting all the nodes in G . There are no. of techniques to create a minimum spanning tree for a weighted graph. For ex. Kruskal's algo. Prim's algorithm. Example :-The given connected weighted graph G is
One of the minimum spanning trees of the graph G is:-
Minimum cost of the spanning tree = 14
