#GPT-4 Conversation #1100551464667054110

1 messages · Page 1 of 1 (latest)

civic epochBOT
cunning bluff
#

create a program perform create, update , delete operation in a Binary Search Tree, it should also include the auto balancing

civic epochBOT
# cunning bluff create a program perform create, update , delete operation in a Binary Search Tr...

Below is a Python program that demonstrates create, update, and delete operations on an AVL tree, which is a balanced binary search tree that automatically maintains balance during insertions and deletions.

class TreeNode:
    def __init__(self, key, left=None, right=None, height=1):
        self.key = key
        self.left = left
        self.right = right
        self.height = height


class AVLTree:
    def insert(self, root, key):
        if not root:
            return TreeNode(key)

        if key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
        balance = self.getBalance(root)

        if balance > 1:
            if key < root.left.key:
                return self.rotateRight(root)
            else:
                root.left = self.rotateLeft(root.left)
                return self.rotateRight(root)

        if balance < -1:
            if key > root.right.key:
                return self.rotateLeft(root)
            else:
                root.right = self.rotateRight(root.right)
                return self.rotateLeft(root)

        return root

    def delete(self, root, key):
        if not root:
            return root

        if key < root.key:
            root.left = self.delete(root.left, key)
        else:
            if key > root.key:
                root.right = self.delete(root.right, key)
            else:
                if root.left is None:
                    temp, root = root.right, None
                    return temp
                elif root.right is None:
                    temp, root = root.left, None
                    return temp

                temp = self.getMinimum(root.right)
                root.key = temp.key
                root.right = self.delete(root.right, temp.key)

        if root is None:
            return root

        root.height =
#

1 + max(self.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)

    if balance > 1:
        if self.getBalance(root.left) < 0:
            root.left = self.rotateLeft(root.left)
        return self.rotateRight(root)

    if balance < -1:
        if self.getBalance(root.right) > 0:
            root.right = self.rotateRight(root.right)
        return self.rotateLeft(root)

    return root

def update(self, root, old_key, new_key):
    root = self.delete(root, old_key)
    return self.insert(root, new_key)

def leftRotation(self, root):
    new_root = root.right
    temp = new_root.left

    new_root.left = root
    root.right = temp

    root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
    new_root.height = 1 + max(self.getHeight(new_root.left), self.getHeight(new_root.right))

    return new_root

def rightRotation(self, root):
    new_root = root.left
    temp = new_root.right

    new_root.right = root
    root.left = temp

    root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
    new_root.height = 1 + max(self.getHeight(new_root.left), self.getHeight(new_root.right))

    return new_root

def getHeight(self, root):
    if not root:
        return 0
    return root.height

def getBalance(self, root):
    if not root:
        return 0
    return self.getHeight(root.left) - self.getHeight(root.right)

def getMinimum(self, root):
    if root is None or root.left is None:
        return root
    return self.getMinimum(root.left)

def preOrder(root):
if not root:
return
print("{0} ".format(root.key), end="")
preOrder(root.left)
preOrder(root.right)


You can create, update, and delete nodes of an AVL tree and it will always remain balanced. This code snippet allows you to perform these operati
#

ons using insert(), delete() and update() methods.

cunning bluff
#

what is the time now ?

civic epochBOT
cunning bluff
#

what is the time now ?

civic epochBOT
cunning bluff
#

how do I earn more credits ?