Тема: При вставке дерево AVL не вращается.

Ответить в теме
Показано с 1 по 1 из 1
  1. Вверх #1
    Новичок
    Пол
    Мужской
    Возраст
    25
    Сообщений
    17
    Репутация
    10

    По умолчанию При вставке дерево AVL не вращается.

    Я пытался сначала добавить 0, затем 1, затем 2, но всегда терпит неудачу, когда я добавляю 2. Когда я добавляю 2, вместо поворота влево и 1 становится новым корнем, корень остается 0. Я не думаю, что это проблема с моими процедурами вращения, потому что я тестировал их и еще не провалил тест.
    Код:
    public void updateHeight(BSTNode<T> node) {
        if (node != null) {
            int leftHeight = height(node.getLeft());
            int rightHeight = height(node.getRight());
            int realHeight = Math.max(leftHeight, rightHeight) + 1;
            node.setHeight(realHeight);
        }
    }
    
    public int balanceFactor(BSTNode<T> node) {
        if (node == null)
            return 0;
        return height(node.getRight()) - height(node.getLeft());
    }
    
    public BSTNode<T> rotateLeft(BSTNode<T> node) {
        BSTNode<T> rightNode = node.getRight();
        BSTNode<T> rightLeftNode = rightNode.getLeft();
    
        node.setRight(rightLeftNode);
    
        if (rightLeftNode != null)
            rightNode.getLeft().setParent(node);
        rightNode.setLeft(node);
    
        rightNode.setParent(node.getParent());
        node.setParent(rightNode);
    
        if (rightNode.getParent() != null && node.getData().compareTo(rightNode.getParent().getData()) > 0)
            rightNode.getParent().setLeft(rightNode);
        else if (rightNode.getParent() != null)
            rightNode.getParent().setRight(rightNode);
    
        updateHeight(node.getRight());
        updateHeight(node.getLeft());
        updateHeight(node);
        updateHeight(node.getParent());
    
        return rightNode;
    }
    
    public BSTNode<T> rotateRight(BSTNode<T> node) {
        BSTNode<T> leftNode = node.getLeft();
        BSTNode<T> leftRightNode = leftNode.getRight();
    
        if (leftRightNode != null)
            leftNode.getRight().setParent(node);
    
        node.setLeft(leftRightNode);
        leftNode.setRight(node);
    
        leftNode.setParent(node.getParent());
        node.setParent(leftNode);
    
        if (leftNode.getParent() != null && node.getData().compareTo(leftNode.getParent().getData()) > 0)
            leftNode.getParent().setLeft(leftNode);
        else if (leftNode.getParent() != null)
            leftNode.getParent().setRight(leftNode);
    
        node = leftNode;
        updateHeight(node.getRight());
        updateHeight(node.getLeft());
        updateHeight(node);
        updateHeight(node.getParent());
    
        return node;
    }
    
    public void add(T t) {
        BSTNode<T> newNode = new BSTNode<T>(t, null, null);
        if (root == null)
            root = newNode;
        else
            addHelper(root, newNode);
    }
    
    private void addHelper(BSTNode<T> currNode, BSTNode<T> newNode) {
        if (currNode == null)
            return;
        if (newNode.getData().compareTo(currNode.getData()) < 0) {
            if (currNode.getLeft() == null) {
                currNode.setLeft(newNode);
                newNode.setParent(currNode);
            } else
                addHelper(currNode.getLeft(), newNode);
        } else {
            if (currNode.getRight() == null) {
                currNode.setRight(newNode);
                newNode.setParent(currNode);
            } else
                addHelper(currNode.getRight(), newNode);
        }
    
        int balance = balanceFactor(currNode);
        System.out.println(newNode.getData() + " " + currNode.getData() + " " + balance);
    
        if (balance < -1) {
            if (balanceFactor(currNode.getLeft()) > 0) {
                rotateLeft(currNode.getLeft());
            }
            rotateRight(currNode);
        } else if (balance > 1) {
            if (balanceFactor(currNode.getRight()) < 0) {
                rotateRight(currNode.getRight());
            }
            rotateLeft(currNode);
        }
    
        updateHeight(currNode);
    }
    Я не уверен, что происходит не так. Я прочитал эту статью от scaler, чтобы узнать об этом больше. Мне также непонятно, почему оператор печати выводит дважды при добавлении 2 по какой-то причине.


Ответить в теме

Похожие темы

Метки этой темы

Социальные закладки

Социальные закладки

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения