Question

Not asking for code.

For each of the following lists, construct both an AVL tree and a 2-3 tree by inserting their elements successively, starting with the empty tree. 1, 2, 3, 4, 5, 6 6, 3, 2, 1, 4, 5

Answer 1

AVL is a self balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. If at any time they differ by more than one, rebalancing is done to correct this.

Balancing Factor (BF) for a node in a tree is difference between height of its left subtree and height of its right subtree. In an AVL tree, BF is either -1, 0 or 1. If on insertion into an AVL tree if BF for a node is less than -1 or greater than 1 then rebalancing needs to be done to rebalance the AVL tree.

AVL tree insertion is illustrated below.

List #1: 1, 2, 3, 4, 5, 6

AVL Tree Insơction LIST#1: 1, 2, 3, 4, 5, 6 TREE ACTION BF:0-0 O 2. bFso-1.-1-ㄧㄧㄧㄣ 3, ROTATE NT 3 e) Inbent

TREE AcTION BFao RSTATE ert Fao TATE Fio 3

List #2: 6, 3, 2, 1, 4, 5

AVL TREE INSERTIo N TREE ACTION InitinlEmpty BF: 舅任。 2 3 8FA0 3 2

TREE 3 BF: 2-220 6f20 15-0

2–3 tree is a tree in which every node with children has either two children and one data element or three children (3-nodes) and two data elements. 2-3 tree insertion is illustrated below.

List #1: 1, 2, 3, 4, 5, 6

2-3 lnee Inserrtion LIST #1 : 1ソ3 ) 4 )5,6 ACTIO N TRE E a) Initial Empty 1 2. ert 2 2. 3 1 2

ACTION TREE 2.

List #2: 6, 3, 2, 1, 4, 5

2-3 Tree Inserution LIST#2: ACTION 6,3, 2, i,H,5 TREE a) nitial E mpty 3 e) Insert 4 mse 3 2.

AcTION TREE 3 2. 5