在阵列二叉树删除操作 [英] Delete operation in Array Binary Tree
问题描述
我知道你们要抱怨不得不被一次又一次地问到这个问题。很抱歉，但我还没有发现我在谷歌/＃1 /论坛的答案...等
我创建Java中的数组二叉树（它不是一个搜索的一个）。
1）我的节点具有属性：父母，左，右。它们是父，左子和右子的索引数。我的教授告诉我，像这样做，我不知道为什么，因为你可以寻父的指标和孩子一个公式，我想有人来告诉我如何加入家长的指标/左/右对子级帮我在操作的复杂性。
2），而我只是找不到什么应该是删除操作的复杂性，当你有一个指向数组中的节点。我想在删除一个节点时，所有节点移动到左侧。我认为这是为O（n），我不知道如何改进它。我读过，有些人正在实施与O（log n）的这个操作。但他们不怎么说。 （我想AP preciate任何片段code在Java中）。
*请记住我与从Java的ArrayList的工作。
有些code：
公共类ArrayBinaryTree＆LT; E＆GT;实现二叉树＆LT; E＆GT; {
私有类BTPos＆LT; T＆GT;实现了位置＆LT; T＆GT; {
私人ŧ元素;
私人诠释父母;
私人诠释左;
私人诠释权;
私人诠释指数; / **主要构造* /
公共BTPos（T元素，诠释指数，诠释父，诠释左，右诠释）{
setIndex（索引）;
setElement（元件）;
调用setParent（父）;
setLeft（左）;
setRight（右）;
} / **返回索引* /
公众诠释getIndex（）{
返回指数;
} / **设置索引* /
公共无效setIndex（int i）以{
指数= I;
} / **返回存储在该位置的元素* /
公共ŧgetElement（）{
归元;
} / **设定存储在该位置的元素* /
公共无效setElement（T O）{
元素= O;
} / **返回父* /
公众诠释的getParent（）{
回到父母;
} / **设置索引* /
公共无效调用setParent（int i）以{
父= I;
} / **返回左* /
公众诠释getLeft（）{
返回左;
} / **设置左* /
公共无效setLeft（int i）以{
左= I;
} / **返回正确的* /
公众诠释GetRight时（）{
返回的权利;
} / **设置正确的* /
公共无效setRight（int i）以{
右=我;
}
}
私人列表＆LT; BTPos＆LT; E＆GT;＆GT;树;
私人诠释的大小;
私人最终诠释MAX_SIZE; / **创建一个空的二叉树。 * /
公共ArrayBinaryTree（）{
this.MAX_SIZE = 100;
this.tree =新的ArrayList＆LT; BTPos＆LT; E＆GT;＆GT;（this.MAX_SIZE）;
this.size = 0;
}
}
具有指标公式
好：1）只有当你有一个固定的布局工作。但是，如果你没有一个平衡树，这是你的阵列中的空间赤身。 2）解决在O（log n）的的删除需要一个平衡树（如果没有一个BST - 我不知道）。你可以找到一个解释如何做到这一点很容易地使用谷歌。）
I know you guys are going to complain about having this question being asked again and again. Sorry, but I have not found my answer in Google/Stackoverflow/Forums... etc
I am creating an Array Binary Tree (it's not a search one) in Java.
1) My node has the attributes: parent, left and right. Which are the number of the indexes of the parent, left child and right child. My professor told me to do it like this, I don't know why because you can find the indexes of the parent and children with a formula, and I would like someone to tell me how adding the indexes of parent/left/right whould help me in the complexity of the operations.
2) And I just can't find what should be the complexity of the delete operation when you have a pointer to the node in the array. I'm thinking in moving all the nodes to the left when deleting a node. I think it's O(n) and I don't know how to improve it. I've read that some people are implementing this operation with O(log n). But they don't say how. (I would appreciate any snippet code in Java).
*Keep in mind I am working with an ArrayList from Java.
Some Code:
public class ArrayBinaryTree<E> implements BinaryTree<E> {
private class BTPos<T> implements Position<T> {
private T element;
private int parent;
private int left;
private int right;
private int index;
/** Main constructor */
public BTPos(T element, int index, int parent, int left, int right) {
setIndex(index);
setElement(element);
setParent(parent);
setLeft(left);
setRight(right);
}
/** Returns the index */
public int getIndex() {
return index;
}
/** Sets the index */
public void setIndex(int i) {
index = i;
}
/** Returns the element stored at this position */
public T getElement() {
return element;
}
/** Sets the element stored at this position */
public void setElement(T o) {
element = o;
}
/** Returns the parent */
public int getParent() {
return parent;
}
/** Sets the index */
public void setParent(int i) {
parent = i;
}
/** Returns the left */
public int getLeft() {
return left;
}
/** Sets the left */
public void setLeft(int i) {
left = i;
}
/** Returns the right */
public int getRight() {
return right;
}
/** Sets the right */
public void setRight(int i) {
right = i;
}
}
private List<BTPos<E>> tree;
private int size;
private final int MAX_SIZE;
/** Creates an empty binary tree. */
public ArrayBinaryTree() {
this.MAX_SIZE = 100;
this.tree = new ArrayList<BTPos<E>>(this.MAX_SIZE);
this.size = 0;
}
}
Well on 1) having a formula for the indexes only works if you have a fixed layout. However if you don't have a balanced tree this is wast of space in your array. On 2) solving the delete on O (log n) requires a balanced tree (If not a BST - I'm not sure). You can find an explanation how to do this easily using Google ;).
这篇关于在阵列二叉树删除操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
