可视化自平衡二叉树 (AVL-tree)
Visualizing self-balancing binary tree (AVL-tree)
我编写了一个可视化二叉搜索树的应用程序。现在我正在尝试修改它以可视化 自平衡 二叉搜索树。我有平衡方法,但是更新每个节点中的 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;
}
我建议不要将这些额外信息存储在节点中,因为更新这些信息可能会很痛苦。而是在需要绘制树时动态确定此信息。
例如,您可以只保留 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();
我编写了一个可视化二叉搜索树的应用程序。现在我正在尝试修改它以可视化 自平衡 二叉搜索树。我有平衡方法,但是更新每个节点中的 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;
}
我建议不要将这些额外信息存储在节点中,因为更新这些信息可能会很痛苦。而是在需要绘制树时动态确定此信息。
例如,您可以只保留 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();