可视化自平衡二叉树 (AVL-tree)

Question

我编写了一个可视化二叉搜索树的应用程序。现在我正在尝试修改它以可视化 自平衡 二叉搜索树。我有平衡方法，但是更新每个节点中的 depth 和 index vars 似乎有一些问题，它们用于计算绘制节点的位置。在尝试了很多不同的东西之后，代码变得很难理解，但我怀疑有一个简单的解决方案，所以我想我会在这里问一下。

示例运行：输入节点 50、60、70。树应该如下所示：

60(depth = 0, index = 1, height = 1, size = 2), 
50(depth = 1, index = 1, height=0, size = 0) and 
70(depth = 1, index = 2, height = 0, size = 0)
    60
  50  70

但是，它看起来像这样：

50(depth = 0, index = 1, height = 0, size = 0)
60(depth = 1, index = 2, height = 2, size = 2)
70(depth = 2, index = 4, height = 0, size = 0)
50
  60
    70

public void setDrawPosition(Node node) {
        node.drawX = (node.index * DrawPanel.width) / ((int)Math.pow(2,node.depth) + 1);
        node.drawY = node.depth * DrawPanel.height / (depth+1);
    }
    
    public void addNode(int val) {
        root = addNode(val, root);
        System.out.println("tree depth is now: " + this.depth);
        root.height = this.depth;
    }

这是添加节点的方法：

private Node addNode(int val, Node node) { 
        if (node == null) {
            return new Node(val, 0, 0, 1, 0); // Node(int val, int depth, int size, int index, int height)
        }
        if (val < node.key) {
           node.left = addNode(val, node.left);
           node.left.depth = node.depth + 1;
           if(node.left.depth > this.depth) {
                depth = node.left.depth;
                root.height = node.left.depth;
            }
           node.left.parent = node;
           node.left.index = (node.index*2)-1;
           if (height(node.left) - height(node.right) == 2) {
               if (val < node.left.key)
                   node = rotateWithLeftChild(node);
               else
                   node = doubleWithLeftChild(node);
           }
           
        } else {
           node.right = addNode(val, node.right);
           node.right.depth = node.depth + 1;
           if(node.right.depth > this.depth) {
                depth = node.right.depth;
                root.height = node.right.depth;
            }
           node.right.parent = node;
           node.right.index = (node.index*2);
           if (height( node.right ) - height( node.left ) == 2) {
               if (val > node.right.key) 
                   node = rotateWithRightChild(node);              
               else 
                   node = doubleWithRightChild(node);
           }
        } 
        node.height = max( height( node.left ), height( node.right ) ) + 1;
        node.size++;
        return node;
    }

其中一个简单的旋转（它们是相似的）：

   private Node rotateWithRightChild(Node k1) {
       Node k2 = k1.right;
       k1.right = k2.left;
       k2.left = k1;
       k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
       k2.height = max( height( k2.right ), k1.height ) + 1;
       
       return k2;
   }

Answer 1

我建议不要将这些额外信息存储在节点中，因为更新这些信息可能会很痛苦。而是在需要绘制树时动态确定此信息。

例如，您可以只保留 val、left 和 right 作为 Node 实例的属性，并定义一个递归方法来计算高度当前节点。然后实际的绘制方法可以使用它来获取树的整体高度，并使用广度优先遍历来获取绘制树所需的所有其他信息。

下面是一些简化“绘图”的代码：只是逐行输出，但使用适当的缩进。我觉得适应你的绘图机制应该很简单：

import java.util.ArrayList;

class Node {
    int val;
    Node left;
    Node right;

    Node(int val) {
        this.val = val;
        left = right = null;
    }

    Node add(int val) { 
        return val < this.val
           ? left != null ? left.add(val)
                          : (left = new Node(val))
           : right != null ? right.add(val)
                           : (right = new Node(val));
    }

    int getHeight() {
        return 1 + Math.max(
            left == null ? 0 : left.getHeight(),
            right == null ? 0 : right.getHeight()
        );
    }

    void draw() {
        int colWidth = 5;
        int height = getHeight();
        int colDistance = (int) Math.pow(2, height);
        ArrayList<Node> level = new ArrayList<Node>();
        level.add(this);
        while (colDistance > 0) {
            ArrayList<Node> nextLevel = new ArrayList<Node>();
            String line = "";
            int col = colDistance / 2 - 1;
            for (int i = 0; i < level.size(); i++) {        
                Node node = level.get(i);
                if (node == null) {
                    nextLevel.add(null);
                    nextLevel.add(null);
                } else {
                    if (col > 0) { // pad string
                        line = String.format("%-" + (col*colWidth) + "s", line);
                    }
                    line += Integer.toString(node.val);
                    nextLevel.add(node.left);
                    nextLevel.add(node.right);
                }
                col += colDistance;
            }
            System.out.println(line);
            level = nextLevel;
            colDistance /= 2;
        }
    }
}

演示使用：

    Node root = new Node(40);
    root.add(50);
    root.add(30);
    root.add(20);
    root.add(60);
    root.add(35);
    root.draw();

可视化自平衡二叉树 (AVL-tree)

Visualizing self-balancing binary tree (AVL-tree)

java

tree

binary-search-tree

avl-tree

depth