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

huangapple go评论76阅读模式
英文:

Visualizing self-balancing binary tree (AVL-tree)

问题

我已经为可视化二叉搜索树编写了一个应用程序。现在我正在尝试修改它以可视化自平衡二叉搜索树。我有平衡方法,但似乎在更新每个节点中用于计算节点绘制位置的深度索引变量时存在一些问题。在尝试了许多不同的方法后,代码变得相当难以理解,但我怀疑存在着一个简单的解决方案,所以我想在这里提问。

示例运行:输入节点 50、60、70。树应该看起来像这样:

60(深度=0,索引=1,高度=1,大小=2),
50(深度=1,索引=1,高度=0,大小=0)和
70(深度=1,索引=2,高度=0,大小=0)
    60
  50  70 

但实际上,它看起来是这样的:

50(深度=0,索引=1,高度=0,大小=0)
60(深度=1,索引=2,高度=2,大小=2)
70(深度=2,索引=4,高度=0,大小=0)
50
  60
    70

以下是 setDrawPositionaddNode 方法的部分代码:

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;
}

以下是 addNode 方法的代码:

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;
}
英文:

I have written an application for visualizing a binary search tree. Now I am attempting to modify it to visualize a self-balancing binary search tree. I have the balancing methods, but there seems to be some problems with updating the depth and index vars in each node, which are used to calculate the draw position of the nodes. The code is getting quite difficult to wrap my head around after trying a bunch of different things, but I suspect there is a simple solution, so I thought i'd ask here.

Example run: Input nodes 50, 60, 70. Tree should look like this:

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 

But instead, it looks like this:

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(&quot;tree depth is now: &quot; + this.depth);
root.height = this.depth;
}

Here's the addNode-method:

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 &lt; node.key) {
node.left = addNode(val, node.left);
node.left.depth = node.depth + 1;
if(node.left.depth &gt; 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 &lt; 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 &gt; 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 &gt; node.right.key) 
node = rotateWithRightChild(node);              
else 
node = doubleWithRightChild(node);
}
} 
node.height = max( height( node.left ), height( node.right ) ) + 1;
node.size++;
return node;
}

One of the simple rotations (they are similar):

   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;
}

答案1

得分: 1

我建议不要将这个额外信息与节点一起存储,因为保持信息更新可能会很麻烦。相反,每当您需要绘制树时,动态确定这些信息。

例如,您可以仅将 valleftright 作为 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();
英文:

I would suggest to not store this extra information with the nodes, as it can be a pain to keep that information updated. Instead determine this information dynamically whenever you need to draw the tree.

For instance, you could keep only val, left and right as properties of a Node instance, and define a recursive method to calculate the height of the current node. Then the actual drawing method could use that to get the overall height of the tree, and use a breadth first traversal to get all other needed information to draw the tree.

Here is some code that does a simplified "draw": just an output line by line, but using appropriate indents. I think it should be simple to adapt to your drawing mechanism:

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 &lt; 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&lt;Node&gt; level = new ArrayList&lt;Node&gt;();
level.add(this);
while (colDistance &gt; 0) {
ArrayList&lt;Node&gt; nextLevel = new ArrayList&lt;Node&gt;();
String line = &quot;&quot;;
int col = colDistance / 2 - 1;
for (int i = 0; i &lt; level.size(); i++) { 		
Node node = level.get(i);
if (node == null) {
nextLevel.add(null);
nextLevel.add(null);
} else {
if (col &gt; 0) { // pad string
line = String.format(&quot;%-&quot; + (col*colWidth) + &quot;s&quot;, line);
}
line += Integer.toString(node.val);
nextLevel.add(node.left);
nextLevel.add(node.right);
}
col += colDistance;
}
System.out.println(line);
level = nextLevel;
colDistance /= 2;
}
}
}

Demo use:

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

huangapple
  • 本文由 发表于 2020年10月5日 17:15:12
  • 转载请务必保留本文链接:https://go.coder-hub.com/64205725.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定