avl-tree.spec.js

const AvlTree = require('./avl-tree.js');

describe('AvlTree', () => {
  let tree;

  beforeEach(() => {
    tree = new AvlTree();
  });

  describe('#contructor', () => {
    it('should initialize', () => {
      expect(tree).not.toBe(null);
    });
  });

  describe('#add', () => {
    it('should add a node', () => {
      expect(tree.size).toBe(0);
      const n1 = tree.add(1);
      expect(tree.size).toBe(1);
      expect(n1.height).toBe(0);
    });

    it('should rebalance asc inserted nodes (LL Rotation)', () => {
      tree.add(1);
      const n = tree.add(2);
      tree.add(3);

      expect(n.toValues()).toMatchObject({
        value: 2, left: 1, right: 3, parent: null,
      });

      expect(tree.toArray()).toEqual([2, 1, 3, null, null, null, null]);
      expect(tree.root).toBe(n);
    });

    it('should rebalance desc inserted nodes (RR Rotation)', () => {
      tree.add(3);
      const n = tree.add(2);
      tree.add(1);

      expect(n.toValues()).toMatchObject({
        value: 2, left: 1, right: 3, parent: null,
      });
      expect(tree.root).toBe(n);
    });

    it('should rebalance with LR Rotation', () => {
      tree.add(3);
      tree.add(1);
      const n = tree.add(2);

      expect(n.toValues()).toMatchObject({
        value: 2, left: 1, right: 3, parent: null,
      });
      expect(tree.root).toBe(n);
    });


    it('should rebalance with RL Rotation', () => {
      tree.add(1);
      tree.add(3);
      const n = tree.add(2);

      expect(n.toValues()).toMatchObject({
        value: 2, left: 1, right: 3, parent: null,
      });
      expect(tree.root).toBe(n);
    });

    it('should not balance', () => {
      [30, 20, 40, 10, 50].forEach(v => tree.add(v));

      expect(tree.toArray()).toEqual([
        30,
        20, 40,
        10, null, null, 50,
        null, null, null, null,
      ]);

      expect(tree.find(40).balanceFactor).toBe(-1); // l: 0, r: 1, bf: -1
      expect(tree.find(20).balanceFactor).toBe(1); // l: 1, r: 0, bf: 1
      expect(tree.find(30).balanceFactor).toBe(0); // l: 2, r: 2, bf: 0
    });
  });

  describe('#remove', () => {
    it('should rebalance asc inserted nodes (LL Rotation)', () => {
      tree.add(1);
      tree.add(-1);
      const n = tree.add(2);
      tree.add(3);

      tree.remove(-1);

      expect(n.toValues()).toMatchObject({
        value: 2, left: 1, right: 3, parent: null,
      });

      expect(tree.root).toBe(n);
      expect(tree.toArray()).toEqual([2, 1, 3, null, null, null, null]);
    });

    it('should rebalance desc inserted nodes (RR Rotation)', () => {
      tree.add(3);
      tree.add(4);
      const n = tree.add(2);
      tree.add(1);

      tree.remove(4);

      expect(n.toValues()).toMatchObject({
        value: 2, left: 1, right: 3, parent: null,
      });
      expect(tree.root).toBe(n);
    });

    it('should rebalance with LR Rotation', () => {
      tree.add(3);
      tree.add(4);
      tree.add(1);
      const n = tree.add(2);

      tree.remove(4);

      expect(n.toValues()).toMatchObject({
        value: 2, left: 1, right: 3, parent: null,
      });
      expect(tree.root).toBe(n);
    });


    it('should rebalance with RL Rotation', () => {
      tree.add(1);
      tree.add(-1);
      tree.add(3);
      const n = tree.add(2);

      tree.remove(-1);

      expect(n.toValues()).toMatchObject({
        value: 2, left: 1, right: 3, parent: null,
      });
      expect(tree.root).toBe(n);
    });
  });

  describe('balance without loosing nodes', () => {
    beforeEach(() => {
      tree.add(16);
      tree.add(4);
      tree.add(32);
      tree.add(8);
      tree.add(2);
    });

    it('should have all nodes', () => {
      expect(tree.toArray()).toEqual([16, 4, 32, 2, 8,
        null, null, null, null, null, null]);
    });

    it('should rebalance and keep all nodes', () => {
      tree.add(1);
      expect(tree.toArray()).toEqual([4, 2, 16, 1, null, 8, 32,
        null, null, null, null, null, null]);
    });
  });

  describe('balancing to the left', () => {
    let n32;
    beforeEach(() => {
      n32 = tree.add(32);
      tree.add(8);
      tree.add(64);
      tree.add(4);
      tree.add(16);
      tree.add(48);
      tree.add(128);
      tree.add(2);
      tree.add(6);
      tree.add(10);
      tree.add(20);
    });

    it('should have all nodes', () => {
      expect(tree.toArray()).toEqual([32, 8, 64, 4, 16, 48, 128, 2, 6, 10, 20,
        null, null, null, null, null, null, null, null, null, null, null, null]);
    });

    it('should rebalance when removing', () => {
      tree.remove(64);
      expect(tree.toArray()).toEqual([32, 8, 128, 4, 16, 48, null, 2, 6, 10, 20,
        null, null, null, null, null, null, null, null, null, null]);
      expect(n32.balanceFactor).toBe(1);
      expect(n32.right.balanceFactor).toBe(1);
      expect(n32.left.balanceFactor).toBe(0);

      tree.remove(48);
      expect(tree.toArray()).toEqual([8, 4, 32, 2, 6, 16, 128, null, null, null, null, 10, 20,
        null, null, null, null, null, null]);
    });
  });

  describe('balancing to the right', () => {
    beforeEach(() => {
      tree.add(8);
      tree.add(4);
      tree.add(32);
      tree.add(2);
      tree.add(16);
      tree.add(64);
      tree.add(10);
      tree.add(20);
      tree.add(60);
      tree.add(70);
    });

    it('should build the tree', () => {
      expect(tree.toArray()).toEqual([8, 4, 32, 2, null, 16, 64, null, null, 10, 20, 60, 70,
        null, null, null, null, null, null, null, null]);
    });

    it('should rebalance right side', () => {
      tree.remove(2);
      expect(tree.toArray()).toEqual([32, 8, 64, 4, 16, 60, 70, null, null, 10, 20,
        null, null, null, null, null, null, null, null]);
    });
  });
});