We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Balanced Trees
  4. Self Balancing Tree
  5. Discussions

Self Balancing Tree

Sort by

recency

|

182 Discussions

|

  • chaupnqfx04448
     + 0 comments

    Python

    class Node:
    def __init__(self, info):
        self.info = info  
        self.left = None  
        self.right = None 
        self.level = None 

    def __str__(self):
        return str(self.info) 
def height(root):
    if root is None:
        return 0
    return max(1+height(root.left),1+height(root.right))
def inOrder(root):
    if root == None:
        return
    inOrder(root.left)
    print (str(root.info)+'(BF='+str(height(root.left)-height(root.right))+')', end=" ")
    inOrder(root.right)
def preOrder(root):
    if root == None:
        return
    print (str(root.info)+'(BF='+str(height(root.left)-height(root.right))+')', end=" ")
    preOrder(root.left)
    preOrder(root.right)
def turnRight(t):
    x=t.left
    y=x.right
    t.left=y
    x.right = t
    return x
def turnLeft(t):
    x=t.right
    y=x.left
    t.right=y
    x.left = t
    return x
def swap(root):
    root.ht = height(root.left) - height(root.right)

    if root.ht > 1:
        if root.left:
            rlt = height(root.left.left) - height(root.left.right)
            if rlt < 0:
                root.left = turnLeft(root.left)
        return turnRight(root)

    if root.ht < -1:
        if root.right:
            rrt = height(root.right.left) - height(root.right.right)
            if rrt > 0:
                root.right = turnRight(root.right)
        return turnLeft(root)

    return root
class BinarySearchTree:
    def __init__(self): 
        self.root = None

#Node is defined as
#self.left (the left child of the node)
#self.right (the right child of the node)
#self.info (the value of the node)

    def insert(self, val):
        #Enter you code here.
        def _insert(root, val):
            if root is None:
                return Node(val)
            if val<root.info:
                root.left = _insert(root.left,val)
            if val>root.info:
                root.right=_insert(root.right,val)
            return swap(root)
        self.root = _insert(self.root,val)
tree = BinarySearchTree()
t = int(input())
arr = list(map(int, input().split()))
k=int(input())
arr.append(k)
for i in range(t+1):
    tree.insert(arr[i])
inOrder(tree.root)
print()
preOrder(tree.root)

  • manceraaxel
     + 0 comments
    import sys

lines = []

for line in sys.stdin:
    if "Exit" == line.rstrip():
        break
    lines.append(line.split("\n")[0])

nol = lines[0]
treeInput = [int(x) for x in lines[1].split(" ")]
toIns = lines[2]

# print(nol)
# print(treeInput)
# print(toIns)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1  # Initially, new nodes have height 1

class AVLTree:
    def __init__(self):
        self.root = None

    def get_height(self, node):
        return node.height if node else 0
    
    def calculate_height(self, node):
        return 1 + max(self.get_height(node.left), self.get_height(node.right))
        
    def getBalance(self, node):
        return self.get_height(node.left) - self.get_height(node.right)

    # Insertion operation - Add your code here
    def insert(self, data):
        self.root = self._insert(self.root, data)

    def _insert(self, node, data):
        if not node:
            return Node(data)

        if data < node.data:
            node.left = self._insert(node.left, data)
        elif data > node.data:
            node.right = self._insert(node.right, data)
        else:
            return
        
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

        bf = self.getBalance(node)

        # An assignment / return statement is needed because, when applying the rotations, the structure of the currennt node's subtree will change, pointing to the new corresponding newly "generated" subrtree.
        ## LL rotation
        if bf > 1 and data < node.left.data:
            return self.rotate_right(node)
        ## LR rotation
        if bf > 1 and data > node.left.data:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        ## RR rotation
        if bf < -1 and data > node.right.data:
            return self.rotate_left(node)
        ## RL rotation
        if bf < -1 and data < node.right.data:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        
        # A return statement is needed because, when applying the rotations, the structure of the currennt node's subtree will change, pointing to the new corresponding newly "generated" subrtree.
        return node
          
    # A return statement is needed because, when applying a rotation, the structure of the currennt node's subtree will change, pointing to the new corresponding newly "generated" subrtree.
    def rotate_right(self, node):
        left = node.left
        left_right = left.right

        left.right = node
        node.left = left_right

        node.height = self.calculate_height(node)
        left.height = self.calculate_height(left)

        return left
    
    def rotate_left(self, node):
        right = node.right
        right_left = right.left

        right.left = node
        node.right = right_left

        node.height = self.calculate_height(node)
        right.height = self.calculate_height(right)

        return right

    # Traversals
    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(f"{node.data}(BF={self.getBalance(node)})", end=" ")
            self.inorder(node.right)

    def postorder(self, node):
        if node is not None:
            print(f"{node.data}(BF={self.getBalance(node)})", end=" ")
            self.postorder(node.left)
            self.postorder(node.right)

    # Function to print BF at each node
    def print_balance(self):
        self.inorder(self.root)
        print("")
        self.postorder(self.root)

tree = AVLTree()
for x in treeInput:
    tree.insert(x)
tree.insert(int(toIns))
tree.print_balance()

  • vaarruntiwari
     + 0 comments

    I keep getting this error and I dont know how to reslove PLease help!! avl.java:319: error: cannot find symbol root=root.insert(root,nv); ^ symbol: method insert(Node,int) location: variable root of type Node 1 error class Solution {

     int Max(int a, int b)
{
    if(a>b)
    {
        return a;
    }
    else 
    {
        return b;
    }
}

  Node leftrot(Node x)
{
    Node y = x.right;
    Node t2 = y.left;

    y.left = x;
    x.right = t2;

    x.ht = Max(height(x.left),height(x.right)+1);
    y.ht = Max(height(x.left),height(x.right)+1);

    return y;
}
  Node rightrot(Node x)
{
    Node y = x.left;
    Node t2 = y.right;

    y.right = x;
    x.left = t2;

    x.ht = Max(height(x.left),height(x.right))+1;
    y.ht = Max(height(x.left),height(x.right))+1;

    return y;

}
 int height(Node n)
{
    if(n == null)
    {
        return 0;
    }
    return n.ht;
}
 int getBalance(Node node)
{
    if(node == null)
    {
        return 0;
    }
    return height(node.left) - height(node.right);
}

 Node insert(Node root,int data)
{
    if(root==null)
    {
         Node node = new Node();
        node.val = val;
        node.ht = 0;
        node.left = null;
        node.right = null;
        return node;
    }
    if(root.val < data)
    {
        root.right = insert(root.right, data);
    }
    else if(root.val > data)
    {
        root.left = insert(root.left, data);
    }
    else
    {
        return root;
    }
    root.ht = Max(height(root.left), height(root.right))+1;

    int balance = getBalance(root);

    if(balance > 1 && data < root.left.val)
    {
        return rightrot(root);
    }
    if(balance < -1 && data > root.right.val)
    {
        return leftrot(root);
    }
    if(balance > 1 && data > root.left.val)
    {
        root.left = leftrot(root.left);
        return rightrot(root);
    }
    if(balance < -1 && data < root.right.val)
    {
        root.right = rightrot(root.right);
        return leftrot(root);
    }
    return root;
}

    avl.java:319: error: cannot find symbol
    root=root.insert(root,nv);
             ^

  • hdezpalexander
     + 0 comments

    Js solution

    class Node { constructor(value) { this.value = value; this.left = null; this.right = null; this.height = 1; } }

    function insert(root, data) { if (!root) return new Node(data);

    if (data < root.value) {
    root.left = insert(root.left, data);
} else {
    root.right = insert(root.right, data);
}

root.height = 1 + Math.max(getHeight(root.left), getHeight(root.right));

const balance = getBalance(root);

if (balance > 1 && data < root.left.value) {
    return rightRotate(root);
}

if (balance < -1 && data > root.right.value) {
    return leftRotate(root);
}

if (balance > 1 && data > root.left.value) {
    root.left = leftRotate(root.left);
    return rightRotate(root);
}

if (balance < -1 && data < root.right.value) {
    root.right = rightRotate(root.right);
    return leftRotate(root);
}

return root;

    }

    function getHeight(node) { return node ? node.height : 0; }

    function getBalance(node) { return node ? getHeight(node.left) - getHeight(node.right) : 0; }

    function rightRotate(y) { const x = y.left; const T2 = x.right;

    x.right = y;
y.left = T2;

y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));

return x;

    }

    function leftRotate(x) { const y = x.right; const T2 = y.left;

    y.left = x;
x.right = T2;

x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));

return y;

    }

    function sortedArrayToAVL(arr) { if (arr.length === 0) return null;

    const mid = Math.floor(arr.length / 2);
const root = new Node(arr[mid]);

root.left = sortedArrayToAVL(arr.slice(0, mid));
root.right = sortedArrayToAVL(arr.slice(mid + 1));

root.height = 1 + Math.max(getHeight(root.left), getHeight(root.right));

const balance = getBalance(root);

if (balance > 1 && getBalance(root.left) >= 0) {
    return rightRotate(root);
}

if (balance < -1 && getBalance(root.right) <= 0) {
    return leftRotate(root);
}

if (balance > 1 && getBalance(root.left) < 0) {
    root.left = leftRotate(root.left);
    return rightRotate(root);
}

if (balance < -1 && getBalance(root.right) > 0) {
    root.right = rightRotate(root.right);
    return leftRotate(root);
}

return root;

    }

    function inOrderTraversal(node, result = []) { if (!node) return result;

    inOrderTraversal(node.left, result);
result.push(``${node.value}(BF=$`{getBalance(node)})`);
inOrderTraversal(node.right, result);

return result;

    }

    function preOrderTraversal(node, result = []) { if (!node) return result;

    result.push(``${node.value}(BF=$`{getBalance(node)})`);
preOrderTraversal(node.left, result);
preOrderTraversal(node.right, result);

return result;

    }

    function processData(input) { const lines = input.trim().split('\n'); const rootPointer = parseInt(lines[0]); const values = lines[1].split(' ').map(Number); const valueToAdd = parseInt(lines[2]);

    let treeAVL;

values.forEach(node => {
    treeAVL = insert(treeAVL, node);
});

treeAVL = insert(treeAVL, valueToAdd);

console.log(inOrderTraversal(treeAVL).join(' '));
console.log(preOrderTraversal(treeAVL).join(' '));

    }

    processData("4\n3 2 4 5\n6");

  • sandipan2018
     + 0 comments

    Fully working python solution

    import sys

lines = []

for line in sys.stdin:
    if 'Exit' == line.rstrip():
        break
    lines.append(line.split('\n')[0])

nol = lines[0]
treeInput = [int(x) for x in lines[1].split(' ')]
toIns = lines[2]
        
# print(nol)
# print(treeInput)
# print(toIns)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1  # Initially, new nodes have height 1

        
class AVLTree:
    def __init__(self):
        self.root = None

    # Insertion operation - Add your code here
    def insert(self,data):   
        self.root=insertnew(self.root,data)
    # Traversals
    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(f"{node.data}(BF={getBalance(node)})", end=" ")
            self.inorder(node.right)
    
    def postorder(self, node):
        if node is not None:
            print(f"{node.data}(BF={getBalance(node)})", end=" ")
            self.postorder(node.left)
            self.postorder(node.right)
            
    # Function to print BF at each node
    def print_balance(self):
        self.inorder(self.root)
        print("")
        self.postorder(self.root)

def insertnew(root,data):
    if root is None:
        return Node(data)
    if root.data<data:
        root.right=insertnew(root.right,data)
    if root.data>data:
        root.left=insertnew(root.left,data)
    root.height=1+max(getheight(root.left),getheight(root.right))
   
# left left case
    if getBalance(root)>1 and data<root.left.data:
        return rotateright(root)
    
    # right right case
    if getBalance(root)<-1 and data>root.right.data: 
        return rotateleft(root)
    
    # left right case
    if getBalance(root)>1 and root.left.data<data:
        root.left=rotateleft(root.left)
        return rotateright(root)
    
    # right left case
    if getBalance(root)<-1 and root.right.data>data:
        root.right=rotateright(root.right)
        return rotateleft(root)
    return root
def getheight(root):
    if root is None:
        return 0
    return root.height
def getBalance(root):
    if root is None:
        return 0
    return (getheight(root.left)-getheight(root.right))

def rotateleft(root):
    y=root.right
    T2=y.left
    # perform rotation
    y.left=root
    root.right=T2
    
    root.height=1+max(getheight(root.left),getheight(root.right))
    y.height=1+max(getheight(y.left),getheight(y.right))
    return y

def rotateright(root):
    y=root.left
    T3=y.right
    # perform rotation
    y.right=root
    root.left=T3
    root.height=1+max(getheight(root.left),getheight(root.right))
    y.height=1+max(getheight(y.left),getheight(y.right))
    return y
tree = AVLTree()

for x in treeInput:
    tree.insert(x)
tree.insert(int(toIns))
tree.print_balance()