# 可视化自平衡二叉树（AVL树）

go评论65阅读模式

Visualizing self-balancing binary tree (AVL-tree)

# 问题

``````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
``````

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

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.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.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);
}
System.out.println(&quot;tree depth is now: &quot; + 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 &lt; node.key) {
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.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

``````import java.util.ArrayList;

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

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

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>();
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) {
} else {
if (col > 0) { // pad string
line = String.format("%-" + (col*colWidth) + "s", line);
}
line += Integer.toString(node.val);
}
col += colDistance;
}
System.out.println(line);
level = nextLevel;
colDistance /= 2;
}
}
}
``````

``````Node root = new Node(40);
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;
}
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;();
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) {
} else {
if (col &gt; 0) { // pad string
line = String.format(&quot;%-&quot; + (col*colWidth) + &quot;s&quot;, line);
}
line += Integer.toString(node.val);
}
col += colDistance;
}
System.out.println(line);
level = nextLevel;
colDistance /= 2;
}
}
}
``````

Demo use:

``````    Node root = new Node(40);
root.draw();
``````

• 本文由 发表于 2020年10月5日 17:15:12
• 转载请务必保留本文链接：https://go.coder-hub.com/64205725.html
• avl-tree
• binary-search-tree
• depth
• java
• tree

go 128

go 58

go 59

go 70