zhwj184
- 浏览: 738259 次
- 性别:
- 来自: 杭州
-
文章分类
最新评论
-
lgh1992314：
a offset: 26b offset: 24c offse ...
java jvm字节占用空间分析 -
ls0609：
语音实现在线听书http://blog.csdn.net/ls ...
Android 语音输入API使用 -
wangli61289：
http://viralpatel-net-tutorials ...
Android 语音输入API使用 -
zxjlwt：
学习了素人派http://surenpi.com
velocity宏加载顺序 -
tt5753：
谢啦........
Lucene的IndexWriter初始化时的LockObtainFailedException的解决方法
最近重新学习数据结构和算法，刚刚看完java版的这几个数据结构，比较浅显易懂，有兴趣的可以自己去调试学习，关于这几个的介绍网上很多。
二叉搜索树，比较简单的树结构了
package com.jwetherell.algorithms.data_structures;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Queue;
/**
* A binary search tree (BST), which may sometimes also be called an ordered or
* sorted binary tree, is a node-based binary tree data structure which has the
* following properties: 1) The left subtree of a node contains only nodes with
* keys less than the node's key. 2) The right subtree of a node contains only
* nodes with keys greater than the node's key. 3) Both the left and right
* subtrees must also be binary search trees.
*
* http://en.wikipedia.org/wiki/Binary_search_tree
*
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public class BinarySearchTree<T extends Comparable<T>> {
private int modifications = 0;
protected static final Random RANDOM = new Random();
protected enum Position { LEFT, RIGHT };
protected Node<T> root = null;
protected int size = 0;
protected INodeCreator<T> creator = null;
/**
* Default constructor.
*/
public BinarySearchTree() { }
/**
* Constructor with external Node creator.
*/
public BinarySearchTree(INodeCreator<T> creator) {
this.creator = creator;
}
/**
* Add value to the tree. Tree can contain multiple equal values.
*
* @param value T to add to the tree.
* @return True if successfully added to tree.
*/
public boolean add(T value) {
Node<T> nodeAdded = this.addValue(value);
return (nodeAdded!=null);
}
/**
* Add value to the tree and return the Node that was added. Tree can
* contain multiple equal values.
*
* @param value T to add to the tree.
* @return Node<T> which was added to the tree.
*/
protected Node<T> addValue(T value) {
Node<T> newNode = null;
if (this.creator == null) newNode = new Node<T>(null, value);
else newNode = this.creator.createNewNode(null, value);
//If root is null, assign
if (root == null) {
root = newNode;
size++;
return newNode;
}
Node<T> node = root;
while (node != null) {
if (newNode.id.compareTo(node.id) <= 0) {
//Less than or equal to goes left
if (node.lesser == null) {
// New left node
node.lesser = newNode;
newNode.parent = node;
size++;
return newNode;
} else {
node = node.lesser;
}
} else {
//Greater than goes right
if (node.greater == null) {
// New right node
node.greater = newNode;
newNode.parent = node;
size++;
return newNode;
} else {
node = node.greater;
}
}
}
return newNode;
}
/**
* Does the tree contain the value.
*
* @param value T to locate in the tree.
* @return True if tree contains value.
*/
public boolean contains(T value) {
Node<T> node = getNode(value);
return (node != null);
}
/**
* Locate T in the tree.
*
* @param value T to locate in the tree.
* @return Node<T> representing first reference of value in tree or NULL if not found.
*/
protected Node<T> getNode(T value) {
Node<T> node = root;
while (node != null && node.id!=null) {
if (value.compareTo(node.id) == 0) {
return node;
} else if (value.compareTo(node.id) < 0) {
node = node.lesser;
} else {
node = node.greater;
}
}
return null;
}
/**
* Rotate tree left at sub-tree rooted at node.
*
* @param node Root of tree to rotate left.
*/
protected void rotateLeft(Node<T> node) {
Position parentPosition = null;
Node<T> parent = node.parent;
if (parent!=null) {
if (node.equals(parent.lesser)) {
//Lesser
parentPosition = Position.LEFT;
} else {
//Greater
parentPosition = Position.RIGHT;
}
}
Node<T> greater = node.greater;
node.greater = null;
Node<T> lesser = greater.lesser;
greater.lesser = node;
node.parent = greater;
node.greater = lesser;
if (lesser!=null) lesser.parent = node;
if (parentPosition!=null) {
if (parentPosition==Position.LEFT) {
parent.lesser = greater;
} else {
parent.greater = greater;
}
greater.parent = parent;
} else {
root = greater;
greater.parent = null;
}
}
/**
* Rotate tree right at sub-tree rooted at node.
*
* @param node Root of tree to rotate left.
*/
protected void rotateRight(Node<T> node) {
Position parentPosition = null;
Node<T> parent = node.parent;
if (parent!=null) {
if (node.equals(parent.lesser)) {
//Lesser
parentPosition = Position.LEFT;
} else {
//Greater
parentPosition = Position.RIGHT;
}
}
Node<T> lesser = node.lesser;
node.lesser = null;
Node<T> greater = lesser.greater;
lesser.greater = node;
node.parent = lesser;
node.lesser = greater;
if (greater!=null) greater.parent = node;
if (parentPosition!=null) {
if (parentPosition==Position.LEFT) {
parent.lesser = lesser;
} else {
parent.greater = lesser;
}
lesser.parent = parent;
} else {
root = lesser;
lesser.parent = null;
}
}
/**
* Get greatest node in sub-tree rooted at startingNode. The
* search does not include startingNode in it's results.
*
* @param startingNode Root of tree to search.
* @return Node<T> which represents the greatest node in the
* startingNode sub-tree or NULL if startingNode has no greater
* children.
*/
protected Node<T> getGreatest(Node<T> startingNode) {
if (startingNode==null) return null;
Node<T> greater = startingNode.greater;
while (greater!=null && greater.id!=null) {
Node<T> node = greater.greater;
if (node!=null && node.id!=null) greater = node;
else break;
}
return greater;
}
/**
* Get least node in sub-tree rooted at startingNode. The
* search does not include startingNode in it's results.
*
* @param startingNode Root of tree to search.
* @return Node<T> which represents the least node in the
* startingNode sub-tree or NULL if startingNode has no lesser
* children.
*/
protected Node<T> getLeast(Node<T> startingNode) {
if (startingNode==null) return null;
Node<T> lesser = startingNode.lesser;
while (lesser!=null && lesser.id!=null) {
Node<T> node = lesser.lesser;
if (node!=null && node.id!=null) lesser = node;
else break;
}
return lesser;
}
/**
* Remove first occurrence of value in the tree.
*
* @param value T to remove from the tree.
* @return True if value was removed from the tree.
*/
public boolean remove(T value) {
Node<T> nodeToRemove = this.removeValue(value);
return (nodeToRemove!=null);
}
/**
* Remove first occurrence of value in the tree.
*
* @param value T to remove from the tree.
* @return Node<T> which was removed from the tree.
*/
protected Node<T> removeValue(T value) {
Node<T> nodeToRemoved = this.getNode(value);
if (nodeToRemoved != null) {
Node<T> replacementNode = this.getReplacementNode(nodeToRemoved);
replaceNodeWithNode(nodeToRemoved,replacementNode);
}
return nodeToRemoved;
}
/**
* Get the proper replacement node according to the binary
* search tree algorithm from the tree.
*
* @param nodeToRemoved Node<T> to find a replacement for.
* @return Node<T> which can be used to replace nodeToRemoved.
* nodeToRemoved should NOT be NULL.
*/
protected Node<T> getReplacementNode(Node<T> nodeToRemoved) {
Node<T> replacement = null;
Node<T> parent = nodeToRemoved.parent;
if (parent == null) {
// Replacing the root node
if (nodeToRemoved.lesser != null && nodeToRemoved.greater == null) {
// Replace with lesser subtree
replacement = nodeToRemoved.lesser;
} else if (nodeToRemoved.greater != null && nodeToRemoved.lesser==null) {
// Replace with greater subtree
replacement = nodeToRemoved.greater;
} else if (nodeToRemoved.greater != null && nodeToRemoved.lesser!=null) {
//Two children
replacement = this.getLeast(nodeToRemoved.greater);
if (replacement==null) replacement = nodeToRemoved.greater;
}
} else if (parent.lesser != null && (parent.lesser.id.compareTo(nodeToRemoved.id) == 0)) {
// If the node to remove is the parent's lesser node, replace
// the parent's lesser node with one of the node to remove's
// lesser/greater subtrees
if (nodeToRemoved.lesser != null && nodeToRemoved.greater == null) {
// Using the less subtree
replacement = nodeToRemoved.lesser;
} else if (nodeToRemoved.greater != null && nodeToRemoved.lesser == null) {
// Using the greater subtree (there is no lesser subtree, no refactoring)
replacement = nodeToRemoved.greater;
} else if (nodeToRemoved.greater != null && nodeToRemoved.lesser!=null) {
//Two children
replacement = this.getLeast(nodeToRemoved.greater);
if (replacement==null) replacement = nodeToRemoved.greater;
}
} else if (parent.greater != null && (parent.greater.id.compareTo(nodeToRemoved.id) == 0)) {
// If the node to remove is the parent's greater node, replace
// the parent's greater node with the node's greater node
if (nodeToRemoved.lesser != null && nodeToRemoved.greater == null) {
// Using the less subtree
replacement = nodeToRemoved.lesser;
} else if (nodeToRemoved.greater != null && nodeToRemoved.lesser == null) {
// Using the greater subtree (there is no lesser subtree, no refactoring)
replacement = nodeToRemoved.greater;
} else if (nodeToRemoved.greater != null && nodeToRemoved.lesser!=null) {
//Two children - use either the greatest child in the lesser branch or the least child in the greater branch
//Add some randomness to deletions, so we don't always use the greatest/least on deletion
if (modifications%2!=0) {
replacement = this.getGreatest(nodeToRemoved.lesser);
if (replacement==null) replacement = nodeToRemoved.lesser;
} else {
replacement = this.getLeast(nodeToRemoved.greater);
if (replacement==null) replacement = nodeToRemoved.greater;
}
modifications++;
}
}
return replacement;
}
/**
* Replace nodeToRemoved with replacementNode in the tree.
*
* @param nodeToRemoved Node<T> to remove replace in the tree. nodeToRemoved
* should NOT be NULL.
* @param replacementNode Node<T> to replace nodeToRemoved in the tree. replacementNode
* can be NULL.
*/
protected void replaceNodeWithNode(Node<T> nodeToRemoved, Node<T> replacementNode) {
if (replacementNode!=null) {
//Save for later
Node<T> replacementNodeLesser = replacementNode.lesser;
Node<T> replacementNodeGreater = replacementNode.greater;
//Replace replacementNode's branches with nodeToRemove's branches
Node<T> nodeToRemoveLesser = nodeToRemoved.lesser;
if (nodeToRemoveLesser!=null && !nodeToRemoveLesser.equals(replacementNode)) {
replacementNode.lesser = nodeToRemoveLesser;
nodeToRemoveLesser.parent = replacementNode;
}
Node<T> nodeToRemoveGreater = nodeToRemoved.greater;
if (nodeToRemoveGreater!=null && !nodeToRemoveGreater.equals(replacementNode)) {
replacementNode.greater = nodeToRemoveGreater;
nodeToRemoveGreater.parent = replacementNode;
}
//Remove link from replacementNode's parent to replacement
Node<T> replacementParent = replacementNode.parent;
if (replacementParent!=null && !replacementParent.equals(nodeToRemoved)) {
Node<T> replacementParentLesser = replacementParent.lesser;
Node<T> replacementParentGreater = replacementParent.greater;
if (replacementParentLesser!=null && replacementParentLesser.equals(replacementNode)) {
replacementParent.lesser = replacementNodeGreater;
if (replacementNodeGreater!=null) replacementNodeGreater.parent = replacementParent;
} else if (replacementParentGreater!=null && replacementParentGreater.equals(replacementNode)) {
replacementParent.greater = replacementNodeLesser;
if (replacementNodeLesser!=null) replacementNodeLesser.parent = replacementParent;
}
}
}
//Update the link in the tree from the nodeToRemoved to the replacementNode
Node<T> parent = nodeToRemoved.parent;
if (parent == null) {
// Replacing the root node
root = replacementNode;
if (root!=null) root.parent = null;
} else if (parent.lesser != null && (parent.lesser.id.compareTo(nodeToRemoved.id) == 0)) {
parent.lesser = replacementNode;
if (replacementNode!=null) replacementNode.parent = parent;
} else if (parent.greater != null && (parent.greater.id.compareTo(nodeToRemoved.id) == 0)) {
parent.greater = replacementNode;
if (replacementNode!=null) replacementNode.parent = parent;
}
size--;
}
/**
* Get number of nodes in the tree.
*
* @return Number of nodes in the tree.
*/
public int size() {
return size;
}
/**
* Validate the tree for all Binary Search Tree invariants.
*
* @return True if tree is valid.
*/
public boolean validate() {
if (root==null) return true;
return validateNode(root);
}
/**
* Validate the node for all Binary Search Tree invariants.
*
* @param node Node<T> to validate in the tree. node should
* NOT be NULL.
* @return True if the node is valid.
*/
protected boolean validateNode(Node<T> node) {
Node<T> lesser = node.lesser;
Node<T> greater = node.greater;
boolean lesserCheck = true;
if (lesser!=null && lesser.id!=null) {
lesserCheck = (lesser.id.compareTo(node.id) <= 0);
if (lesserCheck) lesserCheck = validateNode(lesser);
}
if (!lesserCheck) return false;
boolean greaterCheck = true;
if (greater!=null && greater.id!=null) {
greaterCheck = (greater.id.compareTo(node.id) > 0);
if (greaterCheck) greaterCheck = validateNode(greater);
}
return greaterCheck;
}
/**
* Get an array representation of the tree in breath first search order.
*
* @return breath first search sorted array representing the tree.
*/
@SuppressWarnings("unchecked")
public T[] getBFS() {
Queue<Node<T>> queue = new ArrayDeque<Node<T>>();
T[] values = (T[]) new Comparable[size];
int count = 0;
Node<T> node = root;
while (node!=null) {
values[count++] = node.id;
if (node.lesser!=null) queue.add(node.lesser);
if (node.greater!=null) queue.add(node.greater);
if (!queue.isEmpty()) node = queue.remove();
else node = null;
}
return values;
}
/**
* Get an array representation of the tree in depth first search order.
*
* @return depth first search sorted array representing the tree.
*/
@SuppressWarnings("unchecked")
public T[] getDFS() {
List<Node<T>> added = new ArrayList<Node<T>>(2);
T[] nodes = (T[]) new Comparable[size];
int index = 0;
Node<T> node = root;
while (index < size && node != null) {
Node<T> parent = node.parent;
Node<T> lesser = (node.lesser != null && !added.contains(node.lesser)) ? node.lesser : null;
Node<T> greater = (node.greater != null && !added.contains(node.greater)) ? node.greater : null;
if (parent == null && lesser == null && greater == null) {
if (!added.contains(node)) nodes[index++] = node.id;
break;
}
if (lesser != null) {
node = lesser;
} else {
if (!added.contains(node)) {
nodes[index++] = node.id;
added.add(node);
}
if (greater != null) {
node = greater;
} else if (greater == null && added.contains(node)) {
node = parent;
} else {
// We should not get here. Stop the loop!
node = null;
}
}
}
return nodes;
}
/**
* Get an array representation of the tree in sorted order.
*
* @return sorted array representing the tree.
*/
public T[] getSorted() {
// Depth first search to traverse the tree in order.
return getDFS();
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return TreePrinter.getString(this);
}
protected static class Node<T extends Comparable<T>> {
protected T id = null;
protected Node<T> parent = null;
protected Node<T> lesser = null;
protected Node<T> greater = null;
/**
* Node constructor.
*
* @param parent Parent link in tree. parent can be NULL.
* @param id T representing the node in the tree.
*/
protected Node(Node<T> parent, T id) {
this.parent = parent;
this.id = id;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return "id =" + id +
" parent=" + ((parent != null) ? parent.id : "NULL") +
" lesser=" + ((lesser != null) ? lesser.id : "NULL") +
" greater=" + ((greater != null) ? greater.id : "NULL");
}
}
protected static interface INodeCreator<T extends Comparable<T>> {
/**
* Create a new Node with the following parameters.
*
* @param parent of this node.
* @param id of this node.
* @return new Node
*/
public Node<T> createNewNode(Node<T> parent, T id);
}
protected static class TreePrinter {
public static <T extends Comparable<T>> String getString(BinarySearchTree<T> tree) {
if (tree.root == null) return "Tree has no nodes.";
return getString(tree.root, "", true);
}
private static <T extends Comparable<T>> String getString(Node<T> node, String prefix, boolean isTail) {
StringBuilder builder = new StringBuilder();
if (node.parent!=null) {
String side = "left";
if (node.equals(node.parent.greater)) side = "right";
builder.append(prefix + (isTail ? "└── " : "├── ") + "(" + side + ") " + node.id + "\n");
} else {
builder.append(prefix + (isTail ? "└── " : "├── ") + node.id + "\n");
}
List<Node<T>> children = null;
if (node.lesser != null || node.greater != null) {
children = new ArrayList<Node<T>>(2);
if (node.lesser != null) children.add(node.lesser);
if (node.greater != null) children.add(node.greater);
}
if (children != null) {
for (int i = 0; i < children.size() - 1; i++) {
builder.append(getString(children.get(i), prefix + (isTail ? " " : "│ "), false));
}
if (children.size() >= 1) {
builder.append(getString(children.get(children.size() - 1), prefix + (isTail ? " " : "│ "), true));
}
}
return builder.toString();
}
}
}
平衡二叉树，AVL树，比较复杂了，需要对旋转
package com.jwetherell.algorithms.data_structures;
import java.util.ArrayList;
import java.util.List;
/**
* An AVL tree is a self-balancing binary search tree, and it was the first such data
* structure to be invented. In an AVL tree, the heights of the two child subtrees
* of any node differ by at most one. AVL trees are often compared with red-black trees
* because they support the same set of operations and because red-black trees also take
* O(log n) time for the basic operations. Because AVL trees are more rigidly balanced,
* they are faster than red-black trees for lookup intensive applications. However,
* red-black trees are faster for insertion and removal.
*
* http://en.wikipedia.org/wiki/AVL_tree
*
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public class AVLTree<T extends Comparable<T>> extends BinarySearchTree<T> implements BinarySearchTree.INodeCreator<T> {
private enum Balance { LEFT_LEFT, LEFT_RIGHT, RIGHT_LEFT, RIGHT_RIGHT };
/**
* Default constructor.
*/
public AVLTree() {
this.creator = this;
}
/**
* Constructor with external Node creator.
*/
public AVLTree(INodeCreator<T> creator) {
super(creator);
}
/**
* {@inheritDoc}
*/
@Override
protected Node<T> addValue(T id) {
Node<T> nodeToReturn = super.addValue(id);
AVLNode<T> nodeAdded = (AVLNode<T>) nodeToReturn;
while (nodeAdded!=null) {
nodeAdded.updateHeight();
balanceAfterInsert(nodeAdded);
nodeAdded = (AVLNode<T>) nodeAdded.parent;
}
return nodeToReturn;
}
/**
* Balance the tree according to the AVL post-insert algorithm.
*
* @param node Root of tree to balance.
*/
private void balanceAfterInsert(AVLNode<T> node) {
AVLNode<T> grandParent = (AVLNode<T>) node;
int balanceFactor = grandParent.getBalanceFactor();
if (balanceFactor>1 || balanceFactor<-1) {
AVLNode<T> parent = null;
AVLNode<T> child = null;
Balance balance = null;
if (balanceFactor<0) {
parent = (AVLNode<T>) grandParent.lesser;
balanceFactor = parent.getBalanceFactor();
if (balanceFactor<0) {
child = (AVLNode<T>) parent.lesser;
balance = Balance.LEFT_LEFT;
} else {
child = (AVLNode<T>) parent.greater;
balance = Balance.LEFT_RIGHT;
}
} else {
parent = (AVLNode<T>) grandParent.greater;
balanceFactor = parent.getBalanceFactor();
if (balanceFactor<0) {
child = (AVLNode<T>) parent.lesser;
balance = Balance.RIGHT_LEFT;
} else {
child = (AVLNode<T>) parent.greater;
balance = Balance.RIGHT_RIGHT;
}
}
if (balance == Balance.LEFT_RIGHT) {
//Left-Right (Left rotation, right rotation)
rotateLeft(parent);
rotateRight(grandParent);
} else if (balance == Balance.RIGHT_LEFT) {
//Right-Left (Right rotation, left rotation)
rotateRight(parent);
rotateLeft(grandParent);
} else if (balance == Balance.LEFT_LEFT) {
//Left-Left (Right rotation)
rotateRight(grandParent);
} else {
//Right-Right (Left rotation)
rotateLeft(grandParent);
}
grandParent.updateHeight(); //New child node
child.updateHeight(); //New child node
parent.updateHeight(); //New Parent node
}
}
/**
* {@inheritDoc}
*/
@Override
protected Node<T> removeValue(T value) {
//Find node to remove
Node<T> nodeToRemoved = this.getNode(value);
if (nodeToRemoved != null) {
//Find the replacement node
Node<T> replacementNode = this.getReplacementNode(nodeToRemoved);
//Find the parent of the replacement node to re-factor the height/balance of the tree
AVLNode<T> nodeToRefactor = null;
if (replacementNode!=null) nodeToRefactor = (AVLNode<T>) replacementNode.parent;
if (nodeToRefactor==null) nodeToRefactor = (AVLNode<T>) nodeToRemoved.parent;
if (nodeToRefactor!=null && nodeToRefactor.equals(nodeToRemoved)) nodeToRefactor = (AVLNode<T>) replacementNode;
//Replace the node
replaceNodeWithNode(nodeToRemoved,replacementNode);
//Re-balance the tree all the way up the tree
if (nodeToRefactor!=null) {
while (nodeToRefactor!=null) {
nodeToRefactor.updateHeight();
balanceAfterDelete(nodeToRefactor);
nodeToRefactor = (AVLNode<T>) nodeToRefactor.parent;
}
}
}
return nodeToRemoved;
}
/**
* Balance the tree according to the AVL post-delete algorithm.
*
* @param node Root of tree to balance.
*/
private void balanceAfterDelete(AVLNode<T> node) {
int balanceFactor = node.getBalanceFactor();
if (balanceFactor==-2 || balanceFactor==2) {
if (balanceFactor==-2) {
AVLNode<T> ll = (AVLNode<T>) node.lesser.lesser;
int lesser = (ll!=null)?ll.height:0;
AVLNode<T> lr = (AVLNode<T>) node.lesser.greater;
int greater = (lr!=null)?lr.height:0;
if (lesser>=greater) {
rotateRight(node);
node.updateHeight();
if (node.parent!=null) ((AVLNode<T>)node.parent).updateHeight();
} else {
rotateLeft(node.lesser);
rotateRight(node);
AVLNode<T> p = (AVLNode<T>) node.parent;
if (p.lesser!=null) ((AVLNode<T>)p.lesser).updateHeight();
if (p.greater!=null) ((AVLNode<T>)p.greater).updateHeight();
p.updateHeight();
}
} else if (balanceFactor==2) {
AVLNode<T> rr = (AVLNode<T>) node.greater.greater;
int greater = (rr!=null)?rr.height:0;
AVLNode<T> rl = (AVLNode<T>) node.greater.lesser;
int lesser = (rl!=null)?rl.height:0;
if (greater>=lesser) {
rotateLeft(node);
node.updateHeight();
if (node.parent!=null) ((AVLNode<T>)node.parent).updateHeight();
} else {
rotateRight(node.greater);
rotateLeft(node);
AVLNode<T> p = (AVLNode<T>) node.parent;
if (p.lesser!=null) ((AVLNode<T>)p.lesser).updateHeight();
if (p.greater!=null) ((AVLNode<T>)p.greater).updateHeight();
p.updateHeight();
}
}
}
}
/**
* {@inheritDoc}
*/
@Override
protected boolean validateNode(Node<T> node) {
boolean bst = super.validateNode(node);
if (!bst) return false;
AVLNode<T> avlNode = (AVLNode<T>) node;
int balanceFactor = avlNode.getBalanceFactor();
if (balanceFactor>1 || balanceFactor<-1) {
return false;
}
if (avlNode.isLeaf()) {
if (avlNode.height!=1) return false;
} else {
AVLNode<T> avlNodeLesser = (AVLNode<T>) avlNode.lesser;
int lesserHeight = 1;
if (avlNodeLesser!=null) lesserHeight = avlNodeLesser.height;
AVLNode<T> avlNodeGreater = (AVLNode<T>) avlNode.greater;
int greaterHeight = 1;
if (avlNodeGreater!=null) greaterHeight = avlNodeGreater.height;
if (avlNode.height==(lesserHeight+1) || avlNode.height==(greaterHeight+1)) {
return true;
} else {
return false;
}
}
return true;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return AVLTreePrinter.getString(this);
}
/**
* {@inheritDoc}
*/
@Override
public Node<T> createNewNode(Node<T> parent, T id) {
return (new AVLNode<T>(parent,id));
}
protected static class AVLNode<T extends Comparable<T>> extends Node<T> {
protected int height = 1;
/**
* Constructor for an AVL node
*
* @param parent Parent of the node in the tree, can be NULL.
* @param value Value of the node in the tree.
*/
protected AVLNode(Node<T> parent, T value) {
super(parent,value);
}
/**
* Determines is this node is a leaf (has no children).
*
* @return True if this node is a leaf.
*/
protected boolean isLeaf() {
return ((lesser == null) && (greater == null));
}
/**
* Updates the height of this node based on it's children.
*/
protected void updateHeight() {
int lesserHeight = 0;
int greaterHeight = 0;
if (lesser != null) {
AVLNode<T> lesserAVLNode = (AVLNode<T>) lesser;
lesserHeight = lesserAVLNode.height;
}
if (greater != null) {
AVLNode<T> greaterAVLNode = (AVLNode<T>) greater;
greaterHeight = greaterAVLNode.height;
}
if (lesserHeight>greaterHeight) {
height = lesserHeight+1;
} else {
height = greaterHeight+1;
}
}
/**
* Get the balance factor for this node.
*
* @return An integer representing the balance factor for this node. It will be
* negative if the lesser branch is longer than the greater branch.
*/
protected int getBalanceFactor() {
int lesserHeight = 0;
int greaterHeight = 0;
if (lesser != null) {
AVLNode<T> lesserAVLNode = (AVLNode<T>) lesser;
lesserHeight = lesserAVLNode.height;
}
if (greater != null) {
AVLNode<T> greaterAVLNode = (AVLNode<T>) greater;
greaterHeight = greaterAVLNode.height;
}
return greaterHeight-lesserHeight;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return "value=" + id +
" height=" + height +
" parent=" + ((parent != null) ? parent.id : "NULL") +
" lesser=" + ((lesser != null) ? lesser.id : "NULL") +
" greater=" + ((greater != null) ? greater.id : "NULL");
}
}
protected static class AVLTreePrinter {
public static <T extends Comparable<T>> String getString(AVLTree<T> tree) {
if (tree.root == null) return "Tree has no nodes.";
return getString((AVLNode<T>)tree.root, "", true);
}
public static <T extends Comparable<T>> String getString(AVLNode<T> node) {
if (node == null) return "Sub-tree has no nodes.";
return getString(node, "", true);
}
private static <T extends Comparable<T>> String getString(AVLNode<T> node, String prefix, boolean isTail) {
StringBuilder builder = new StringBuilder();
builder.append(prefix + (isTail ? "└── " : "├── ") + "(" + node.height + ") " + node.id + "\n");
List<Node<T>> children = null;
if (node.lesser != null || node.greater != null) {
children = new ArrayList<Node<T>>(2);
if (node.lesser != null) children.add(node.lesser);
if (node.greater != null) children.add(node.greater);
}
if (children != null) {
for (int i = 0; i < children.size() - 1; i++) {
builder.append(getString((AVLNode<T>)children.get(i), prefix + (isTail ? " " : "│ "), false));
}
if (children.size() >= 1) {
builder.append(getString((AVLNode<T>)children.get(children.size() - 1), prefix + (isTail ? " " : "│ "), true));
}
}
return builder.toString();
}
}
}
BTree 2-3树，分裂和合并部分还是比较简单的
import java.util.Arrays;
import java.util.Comparator;
/**
* B-tree is a tree data structure that keeps data sorted and allows searches,
* sequential access, insertions, and deletions in logarithmic time. The B-tree
* is a generalization of a binary search tree in that a node can have more than
* two children. Unlike self-balancing binary search trees, the B-tree is
* optimized for systems that read and write large blocks of data. It is
* commonly used in databases and file-systems.
*
* http://en.wikipedia.org/wiki/B-tree
*
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public class BTree<T extends Comparable<T>> {
// Default to 2-3 Tree
private int minKeySize = 1;
private int minChildrenSize = minKeySize + 1; //2
private int maxKeySize = 2 * minKeySize; //2
private int maxChildrenSize = maxKeySize + 1; //3
private Node<T> root = null;
private int size = 0;
/**
* Constructor for B-Tree which defaults to a 2-3 B-Tree.
*/
public BTree() { }
/**
* Constructor for B-Tree of ordered parameter.
*
* @param order of the B-Tree.
*/
public BTree(int order) {
this.minKeySize = order;
this.minChildrenSize = minKeySize + 1;
this.maxKeySize = 2 * minKeySize;
this.maxChildrenSize = maxKeySize + 1;
}
/**
* Add value to the tree. Tree can NOT contain multiple equal values.
*
* @param value T to add to the tree.
* @return True if successfully added to tree.
*/
public void add(T value) {
if (root == null) {
root = new Node<T>(null, maxKeySize, maxChildrenSize);
root.addKey(value);
} else {
Node<T> node = root;
while (node != null) {
if (node.numberOfChildren() == 0) {
node.addKey(value);
if (node.numberOfKeys() <= maxKeySize) {
// A-OK
break;
} else {
// Need to split up
split(node);
break;
}
} else {
// navigate
T lesser = node.getKey(0);
if (value.compareTo(lesser) < 0) {
node = node.getChild(0);
continue;
}
int size = node.numberOfKeys();
int last = size - 1;
T greater = node.getKey(last);
if (value.compareTo(greater) > 0) {
node = node.getChild(size);
continue;
}
for (int i = 1; i < node.numberOfKeys(); i++) {
T prev = node.getKey(i - 1);
T next = node.getKey(i);
if (value.compareTo(prev) > 0 && value.compareTo(next) < 0) {
node = node.getChild(i);
break;
}
}
}
}
}
size++;
}
/**
* The node's key size is greater than maxKeySize, split down the middle.
*
* @param node to split.
*/
private void split(Node<T> node) {
int size = node.numberOfKeys();
int medianIndex = size / 2;
T medianValue = node.getKey(medianIndex);
Node<T> left = new Node<T>(null, maxKeySize, maxChildrenSize);
for (int i=0; i<medianIndex; i++) {
left.addKey(node.getKey(i));
}
if (node.numberOfChildren()>0) {
for (int j=0; j<=medianIndex; j++) {
Node<T> c = node.getChild(j);
left.addChild(c);
}
}
Node<T> right = new Node<T>(null, maxKeySize, maxChildrenSize);
for (int i = medianIndex+1; i < size; i++) {
right.addKey(node.getKey(i));
}
if (node.numberOfChildren()>0) {
for (int j=medianIndex+1; j<node.numberOfChildren(); j++) {
Node<T> c = node.getChild(j);
right.addChild(c);
}
}
if (node.parent == null) {
// new root, height of tree is increased
Node<T> newRoot = new Node<T>(null, maxKeySize, maxChildrenSize);
newRoot.addKey(medianValue);
node.parent = newRoot;
root = newRoot;
node = root;
node.addChild(left);
node.addChild(right);
} else {
// Move the median value up to the parent
Node<T> parent = node.parent;
parent.addKey(medianValue);
parent.removeChild(node);
parent.addChild(left);
parent.addChild(right);
if (parent.numberOfKeys() > maxKeySize) split(parent);
}
}
/**
* Does the tree contain the value.
*
* @param value T to locate in the tree.
* @return True if tree contains value.
*/
public boolean contains(T value) {
Node<T> node = getNode(value);
return (node != null);
}
/**
* Get the node with value.
*
* @param value to find in the tree.
* @return Node<T> with value.
*/
private Node<T> getNode(T value) {
Node<T> node = root;
while (node != null) {
T lesser = node.getKey(0);
if (value.compareTo(lesser) < 0) {
if (node.numberOfChildren() > 0) node = node.getChild(0);
else node = null;
continue;
}
int size = node.numberOfKeys();
int last = size - 1;
T greater = node.getKey(last);
if (value.compareTo(greater) > 0) {
if (node.numberOfChildren() > size) node = node.getChild(size);
else node = null;
continue;
}
for (int i = 0; i < size; i++) {
T currentValue = node.getKey(i);
if (currentValue.compareTo(value) == 0) {
return node;
}
int next = i + 1;
if (next <= last) {
T nextValue = node.getKey(next);
if (currentValue.compareTo(value) < 0 && nextValue.compareTo(value) > 0) {
if (next < node.numberOfChildren()) {
node = node.getChild(next);
break;
} else {
return null;
}
}
}
}
}
return null;
}
/**
* Remove the value from the tree.
*
* @param value T to remove from the tree.
* @return True if value was removed from the tree.
*/
public boolean remove(T value) {
Node<T> node = this.getNode(value);
if (node == null) return false;
int index = node.indexOf(value);
node.removeKey(value);
if (node.numberOfChildren()==0) {
//leaf node
if (node.parent!=null && node.numberOfKeys() < minKeySize) {
this.combined(node);
} else if (node.parent==null && node.numberOfKeys()==0) {
//Removing root node with no keys or children
root = null;
}
} else {
//internal node
Node<T> lesser = node.getChild(index);
Node<T> greatest = this.getGreatestNode(lesser);
T replaceValue = this.removeGreatestValue(greatest);
node.addKey(replaceValue);
if (greatest.parent!=null && greatest.numberOfKeys() < minKeySize) {
this.combined(greatest);
}
if (greatest.numberOfChildren() > maxChildrenSize) {
this.split(greatest);
}
}
size--;
return true;
}
/**
* Remove greatest valued key from node.
*
* @param node to remove greatest value from.
* @return value removed;
*/
private T removeGreatestValue(Node<T> node) {
T value = null;
if (node.numberOfKeys()>0) {
value = node.removeKey(node.numberOfKeys()-1);
}
return value;
}
/**
* Get the greatest valued child from node.
*
* @param node child with the greatest value.
* @return Node<T> child with greatest value.
*/
private Node<T> getGreatestNode(Node<T> node) {
while (node.numberOfChildren()>0) {
node = node.getChild(node.numberOfChildren()-1);
}
return node;
}
/**
* Combined children keys with parent when size is less than minKeySize.
*
* @param node with children to combined.
* @return True if combined successfully.
*/
private boolean combined(Node<T> node) {
Node<T> parent = node.parent;
int index = parent.indexOf(node);
int indexOfLeftNeighbor = index - 1;
int indexOfRightNeighbor = index + 1;
Node<T> rightNeighbor = null;
int rightNeighborSize = -minChildrenSize;
if (indexOfRightNeighbor < parent.numberOfChildren()) {
rightNeighbor = parent.getChild(indexOfRightNeighbor);
rightNeighborSize = rightNeighbor.numberOfKeys();
}
// Try to borrow neighbor
if (rightNeighbor != null && rightNeighborSize > minKeySize) {
// Try to borrow from right neighbor
T removeValue = rightNeighbor.getKey(0);
int prev = getIndexOfPreviousValue(parent, removeValue);
T parentValue = parent.removeKey(prev);
T neighborValue = rightNeighbor.removeKey(0);
node.addKey(parentValue);
parent.addKey(neighborValue);
if (rightNeighbor.numberOfChildren()>0) {
node.addChild(rightNeighbor.removeChild(0));
}
} else {
Node<T> leftNeighbor = null;
int leftNeighborSize = -minChildrenSize;
if (indexOfLeftNeighbor >= 0) {
leftNeighbor = parent.getChild(indexOfLeftNeighbor);
leftNeighborSize = leftNeighbor.numberOfKeys();
}
if (leftNeighbor != null && leftNeighborSize > minKeySize) {
// Try to borrow from left neighbor
T removeValue = leftNeighbor.getKey(leftNeighbor.numberOfKeys() - 1);
int prev = getIndexOfNextValue(parent, removeValue);
T parentValue = parent.removeKey(prev);
T neighborValue = leftNeighbor.removeKey(leftNeighbor.numberOfKeys() - 1);
node.addKey(parentValue);
parent.addKey(neighborValue);
if (leftNeighbor.numberOfChildren()>0) {
node.addChild(leftNeighbor.removeChild(leftNeighbor.numberOfChildren()-1));
}
} else if (rightNeighbor != null && parent.numberOfKeys() > 0) {
// Can't borrow from neighbors, try to combined with right neighbor
T removeValue = rightNeighbor.getKey(0);
int prev = getIndexOfPreviousValue(parent, removeValue);
T parentValue = parent.removeKey(prev);
parent.removeChild(rightNeighbor);
node.addKey(parentValue);
for (int i=0; i<rightNeighbor.keysSize; i++) {
T v = rightNeighbor.getKey(i);
node.addKey(v);
}
for (int i=0; i<rightNeighbor.childrenSize; i++) {
Node<T> c = rightNeighbor.getChild(i);
node.addChild(c);
}
if (parent.parent != null && parent.numberOfKeys() < minKeySize) {
// removing key made parent too small, combined up tree
this.combined(parent);
} else if (parent.numberOfKeys() == 0) {
// parent no longer has keys, make this node the new root
// which decreases the height of the tree
node.parent = null;
root = node;
}
} else if (leftNeighbor != null && parent.numberOfKeys() > 0) {
// Can't borrow from neighbors, try to combined with left neighbor
T removeValue = leftNeighbor.getKey(leftNeighbor.numberOfKeys() - 1);
int prev = getIndexOfNextValue(parent, removeValue);
T parentValue = parent.removeKey(prev);
parent.removeChild(leftNeighbor);
node.addKey(parentValue);
for (int i=0; i<leftNeighbor.keysSize; i++) {
T v = leftNeighbor.getKey(i);
node.addKey(v);
}
for (int i=0; i<leftNeighbor.childrenSize; i++) {
Node<T> c = leftNeighbor.getChild(i);
node.addChild(c);
}
if (parent.parent != null && parent.numberOfKeys() < minKeySize) {
// removing key made parent too small, combined up tree
this.combined(parent);
} else if (parent.numberOfKeys() == 0) {
// parent no longer has keys, make this node the new root
// which decreases the height of the tree
node.parent = null;
root = node;
}
}
}
return true;
}
/**
* Get the index of previous key in node.
*
* @param node to find the previous key in.
* @param value to find a previous value for.
* @return index of previous key or -1 if not found.
*/
private int getIndexOfPreviousValue(Node<T> node, T value) {
for (int i = 1; i < node.numberOfKeys(); i++) {
T t = node.getKey(i);
if (t.compareTo(value) >= 0) return i - 1;
}
return node.numberOfKeys() - 1;
}
/**
* Get the index of next key in node.
*
* @param node to find the next key in.
* @param value to find a next value for.
* @return index of next key or -1 if not found.
*/
private int getIndexOfNextValue(Node<T> node, T value) {
for (int i = 0; i < node.numberOfKeys(); i++) {
T t = node.getKey(i);
if (t.compareTo(value) >= 0) return i;
}
return node.numberOfKeys() - 1;
}
/**
* Get number of nodes in the tree.
*
* @return Number of nodes in the tree.
*/
public int size() {
return size;
}
/**
* Validate the tree for all B-Tree invariants.
*
* @return True if tree is valid.
*/
public boolean validate() {
if (root == null) return true;
return validateNode(root);
}
/**
* Validate the node according to the B-Tree invariants.
*
* @param node to validate.
* @return True if valid.
*/
private boolean validateNode(Node<T> node) {
int keySize = node.numberOfKeys();
if (keySize > 1) {
// Make sure the keys are sorted
for (int i = 1; i < keySize; i++) {
T p = node.getKey(i - 1);
T n = node.getKey(i);
if (p.compareTo(n) > 0) return false;
}
}
int childrenSize = node.numberOfChildren();
if (node.parent == null) {
//root
if (keySize > maxKeySize) {
// check max key size. root does not have a min key size
return false;
} else if (childrenSize==0) {
// if root, no children, and keys are valid
return true;
} else if (childrenSize < 2) {
// root should have zero or at least two children
return false;
} else if (childrenSize > maxChildrenSize) {
return false;
}
} else {
//non-root
if (keySize < minKeySize) {
return false;
} else if (keySize > maxKeySize) {
return false;
} else if (childrenSize==0) {
return true;
} else if (keySize != (childrenSize - 1)) {
// If there are chilren, there should be one more child then keys
return false;
} else if (childrenSize < minChildrenSize) {
return false;
} else if (childrenSize > maxChildrenSize) {
return false;
}
}
Node<T> first = node.getChild(0);
// The first child's last key should be less than the node's first key
if (first.getKey(first.numberOfKeys() - 1).compareTo(node.getKey(0)) > 0) return false;
Node<T> last = node.getChild(node.numberOfChildren() - 1);
// The last child's first key should be greater than the node's last key
if (last.getKey(0).compareTo(node.getKey(node.numberOfKeys() - 1)) < 0) return false;
// Check that each node's first and last key holds it's invariance
for (int i = 1; i < node.numberOfKeys(); i++) {
T p = node.getKey(i - 1);
T n = node.getKey(i);
Node<T> c = node.getChild(i);
if (p.compareTo(c.getKey(0)) > 0) return false;
if (n.compareTo(c.getKey(c.numberOfKeys() - 1)) < 0) return false;
}
for (int i=0; i<node.childrenSize; i++) {
Node<T> c = node.getChild(i);
boolean valid = this.validateNode(c);
if (!valid) return false;
}
return true;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return TreePrinter.getString(this);
}
private static class Node<T extends Comparable<T>> {
private T[] keys = null;
private int keysSize = 0;
private Node<T>[] children = null;
private int childrenSize = 0;
private Comparator<Node<T>> comparator = new Comparator<Node<T>>() {
@Override
public int compare(Node<T> arg0, Node<T> arg1) {
return arg0.getKey(0).compareTo(arg1.getKey(0));
}
};
protected Node<T> parent = null;
@SuppressWarnings("unchecked")
private Node(Node<T> parent, int maxKeySize, int maxChildrenSize) {
this.parent = parent;
this.keys = (T[]) new Comparable[maxKeySize+1];
this.keysSize = 0;
this.children = new Node[maxChildrenSize+1];
this.childrenSize = 0;
}
private T getKey(int index) {
return keys[index];
}
private int indexOf(T value) {
for (int i=0; i<keysSize; i++) {
if (keys[i].equals(value)) return i;
}
return -1;
}
private void addKey(T value) {
keys[keysSize++] = value;
Arrays.sort(keys,0,keysSize);
}
private boolean removeKey(T value) {
boolean found = false;
if (keysSize==0) return found;
for (int i=0; i<keysSize; i++) {
if (keys[i].equals(value)) {
found = true;
} else if (found) {
//shift the rest of the keys down
keys[i-1] = keys[i];
}
}
if (found) {
keysSize--;
keys[keysSize] = null;
}
return found;
}
private T removeKey(int index) {
if (index>=keysSize) return null;
T value = keys[index];
keys[index] = null;
for (int i=index+1; i<keysSize; i++) {
//shift the rest of the keys down
keys[i-1] = keys[i];
}
keysSize--;
keys[keysSize] = null;
return value;
}
private int numberOfKeys() {
return keysSize;
}
private Node<T> getChild(int index) {
if (index>=childrenSize) return null;
return children[index];
}
private int indexOf(Node<T> child) {
for (int i=0; i<childrenSize; i++) {
if (children[i].equals(child)) return i;
}
return -1;
}
private boolean addChild(Node<T> child) {
child.parent = this;
children[childrenSize++] = child;
Arrays.sort(children,0,childrenSize,comparator);
return true;
}
private boolean removeChild(Node<T> child) {
boolean found = false;
if (childrenSize==0) return found;
for (int i=0; i<childrenSize; i++) {
if (children[i].equals(child)) {
found = true;
} else if (found) {
//shift the rest of the keys down
children[i-1] = children[i];
}
}
if (found) {
childrenSize--;
children[childrenSize] = null;
}
return found;
}
private Node<T> removeChild(int index) {
if (index>=childrenSize) return null;
Node<T> value = children[index];
children[index] = null;
for (int i=index+1; i<childrenSize; i++) {
//shift the rest of the keys down
children[i-1] = children[i];
}
childrenSize--;
children[childrenSize] = null;
return value;
}
private int numberOfChildren() {
return childrenSize;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("keys=[");
for (int i = 0; i < numberOfKeys(); i++) {
T value = getKey(i);
builder.append(value);
if (i < numberOfKeys() - 1) builder.append(", ");
}
builder.append("]\n");
if (parent != null) {
builder.append("parent=[");
for (int i = 0; i < parent.numberOfKeys(); i++) {
T value = parent.getKey(i);
builder.append(value);
if (i < parent.numberOfKeys() - 1) builder.append(", ");
}
builder.append("]\n");
}
if (children != null) {
builder.append("children=").append(numberOfChildren()).append("\n");
}
return builder.toString();
}
}
private static class TreePrinter {
public static <T extends Comparable<T>> String getString(BTree<T> tree) {
if (tree.root == null) return "Tree has no nodes.";
return getString(tree.root, "", true);
}
private static <T extends Comparable<T>> String getString(Node<T> node, String prefix, boolean isTail) {
StringBuilder builder = new StringBuilder();
builder.append(prefix).append((isTail ? "└── " : "├── "));
for (int i = 0; i < node.numberOfKeys(); i++) {
T value = node.getKey(i);
builder.append(value);
if (i < node.numberOfKeys() - 1) builder.append(", ");
}
builder.append("\n");
if (node.children != null) {
for (int i = 0; i < node.numberOfChildren() - 1; i++) {
Node<T> obj = node.getChild(i);
builder.append(getString(obj, prefix + (isTail ? " " : "│ "), false));
}
if (node.numberOfChildren() >= 1) {
Node<T> obj = node.getChild(node.numberOfChildren() - 1);
builder.append(getString(obj, prefix + (isTail ? " " : "│ "), true));
}
}
return builder.toString();
}
}
}
二叉堆，最简单的树结构实现了
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* A binary heap is a heap data structure created using a binary tree. It can be
* seen as a binary tree with two additional constraints: 1) The shape property:
* the tree is a complete binary tree; that is, all levels of the tree, except
* possibly the last one (deepest) are fully filled, and, if the last level of
* the tree is not complete, the nodes of that level are filled from left to
* right. 2) The heap property: each node is right than or equal to each of its
* children according to a comparison predicate defined for the data structure.
*
* http://en.wikipedia.org/wiki/Binary_heap
*
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public abstract class BinaryHeap<T extends Comparable<T>> {
public enum HeapType { Tree, Array };
public enum Type { MIN, MAX };
/**
* Number of nodes in the heap.
*
* @return Number of nodes in the heap.
*/
public abstract int size();
/**
* Add value to the heap.
*
* @param value to add to the heap.
*/
public abstract void add(T value);
/**
* Does the value exist in the heap. Warning
* this is a O(n) operation.
*
* @param value to locate in the heap.
* @return True if the value is in heap.
*/
public abstract boolean contains(T value);
/**
* Get the heap in array form.
*
* @return array representing the heap.
*/
public abstract T[] getHeap();
/**
* Get the value of the head node from the heap.
*
* @return value of the head node.
*/
public abstract T getHeadValue();
/**
* Remove the head node from the heap.
*
* @return value of the head node.
*/
public abstract T removeHead();
/**
* Validate the heap according to the invariants.
*
* @return True if the heap is valid.
*/
public abstract boolean validate();
public static <T extends Comparable<T>> BinaryHeap<T> createHeap(HeapType type) {
switch (type) {
case Array:
return new BinaryHeapArray<T>();
default:
return new BinaryHeapTree<T>();
}
}
/**
* A binary heap using an array to hold the nodes.
*
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public static class BinaryHeapArray<T extends Comparable<T>> extends BinaryHeap<T> {
private static final int MINIMUM_SIZE = 10;
private Type type = Type.MIN;
private int size = 0;
@SuppressWarnings("unchecked")
private T[] array = (T[]) new Comparable[MINIMUM_SIZE];
/**
* Get the parent index of this index, will return Integer.MIN_VALUE if no parent
* is possible.
*
* @param index of the node to find a parent for.
* @return index of parent node or Integer.MIN_VALUE if no parent.
*/
private static final int getParentIndex(int index) {
if (index>0) return (int) Math.floor((index-1)/2);
else return Integer.MIN_VALUE;
}
/**
* Get the left child index of this index.
*
* @param index of the node to find a left child for.
* @return index of left child node.
*/
private static final int getLeftIndex(int index) {
return 2*index+1;
}
/**
* Get the right child index of this index.
*
* @param index of the node to find a right child for.
* @return index of right child node.
*/
private static final int getRightIndex(int index) {
return 2*index+2;
}
/**
* Constructor for heap, defaults to a min-heap.
*/
public BinaryHeapArray() {
size = 0;
}
/**
* Constructor for heap.
*
* @param type Heap type.
*/
public BinaryHeapArray(Type type) {
this();
this.type = type;
}
/**
* {@inheritDoc}
*/
@Override
public int size() {
return size;
}
/**
* {@inheritDoc}
*/
@Override
public void add(T value) {
if (size>=array.length) {
array = Arrays.copyOf(array, ((size*3)/2)+1);
}
array[size] = value;
heapUp(size++);
}
protected void heapUp(int nodeIndex) {
T value = this.array[nodeIndex];
while (nodeIndex>=0) {
int parentIndex = getParentIndex(nodeIndex);
if (parentIndex<0) break;
T parent = this.array[parentIndex];
if ( (type == Type.MIN && parent != null && value.compareTo(parent) < 0) ||
(type == Type.MAX && parent != null && value.compareTo(parent) > 0)
){
// Node is less than parent, switch node with parent
this.array[parentIndex] = value;
this.array[nodeIndex] = parent;
} else {
nodeIndex = parentIndex;
}
}
}
/**
* {@inheritDoc}
*/
@Override
public boolean contains(T value) {
if (array.length==0) return false;
for (int i=0; i<size; i++) {
T node = array[i];
if (node.equals(value)) return true;
}
return false;
}
/**
* {@inheritDoc}
*/
@Override
public boolean validate() {
if (array.length==0) return true;
return validateNode(0);
}
/**
* Validate the node for the heap invariants.
*
* @param node to validate for.
* @return True if node is valid.
*/
private boolean validateNode(int index) {
T value = this.array[index];
int leftIndex = getLeftIndex(index);
int rightIndex = getRightIndex(index);
//We shouldn't ever have a right node without a left in a heap
if (rightIndex!=Integer.MIN_VALUE && leftIndex==Integer.MIN_VALUE) return false;
if (leftIndex!=Integer.MIN_VALUE && leftIndex<size) {
T left = this.array[leftIndex];
if ((type == Type.MIN && value.compareTo(left) < 0) || (type == Type.MAX && value.compareTo(left) > 0)) {
return validateNode(leftIndex);
} else {
return false;
}
}
if (rightIndex!=Integer.MIN_VALUE && rightIndex<size) {
T right = this.array[rightIndex];
if ((type == Type.MIN && value.compareTo(right) < 0) || (type == Type.MAX && value.compareTo(right) > 0)) {
return validateNode(rightIndex);
} else {
return false;
}
}
return true;
}
/**
* {@inheritDoc}
*/
@Override
@SuppressWarnings("unchecked")
public T[] getHeap() {
T[] nodes = (T[]) new Comparable[size];
if (array.length==0) return nodes;
for (int i=0; i<size; i++) {
T node = this.array[i];
nodes[i] = node;
}
return nodes;
}
/**
* {@inheritDoc}
*/
@Override
public T getHeadValue() {
if (array.length==0) return null;
return array[0];
}
/**
* {@inheritDoc}
*/
@Override
public T removeHead() {
T result = null;
if (array.length==0) return result;
//Get the root element in the array
result = array[0];
//Save the last element of the array and then null out the last element's index
int lastIndex = --size;
T lastNode = array[lastIndex];
array[size] = null;
//No more elements in the heap
if (size<=0) {
return result;
}
//Put the last element in the root's spot
array[0] = lastNode;
if (size>=MINIMUM_SIZE && size<array.length/2) {
array = Arrays.copyOf(array, size);
}
//Heap down from the root
heapDown(0);
return result;
}
protected void heapDown(int index) {
T value = this.array[index];
int leftIndex = getLeftIndex(index);
int rightIndex = getRightIndex(index);
T left = (leftIndex!=Integer.MIN_VALUE && leftIndex<this.size)?this.array[leftIndex]:null;
T right = (rightIndex!=Integer.MIN_VALUE && rightIndex<this.size)?this.array[rightIndex]:null;
if (left == null && right == null) {
// Nothing to do here
return;
}
T nodeToMove = null;
int nodeToMoveIndex = -1;
if ( (type == Type.MIN && left != null && right != null && value.compareTo(left) > 0 && value.compareTo(right) > 0) ||
(type == Type.MAX && left != null && right != null && value.compareTo(left) < 0 && value.compareTo(right) < 0)
) {
// Both children are greater/lesser than node
if ((type == Type.MIN && right.compareTo(left) < 0) ||
(type == Type.MAX && right.compareTo(left) > 0)
) {
// Right is greater/lesser than left
nodeToMove = right;
nodeToMoveIndex = rightIndex;
} else if ( (type == Type.MIN && left.compareTo(right) < 0) ||
(type == Type.MAX && left.compareTo(right) > 0)
){
// Left is greater/lesser than right
nodeToMove = left;
nodeToMoveIndex = leftIndex;
} else {
// Both children are equal, use right
nodeToMove = right;
nodeToMoveIndex = rightIndex;
}
} else if ( (type == Type.MIN && right != null && value.compareTo(right) > 0) ||
(type == Type.MAX && right != null && value.compareTo(right) < 0)
) {
// Right is greater/lesser than node
nodeToMove = right;
nodeToMoveIndex = rightIndex;
} else if ( (type == Type.MIN && left != null && value.compareTo(left) > 0) ||
(type == Type.MAX && left != null && value.compareTo(left) < 0)
) {
// Left is greater/lesser than node
nodeToMove = left;
nodeToMoveIndex = leftIndex;
}
// No node to move, stop recursion
if (nodeToMove == null) return;
// Re-factor heap sub-tree
this.array[nodeToMoveIndex] = value;
this.array[index] = nodeToMove;
heapDown(nodeToMoveIndex);
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return HeapPrinter.getString(this);
}
protected static class HeapPrinter {
public static <T extends Comparable<T>> String getString(BinaryHeapArray<T> tree) {
if (tree.array.length==0) return "Tree has no nodes.";
T root = tree.array[0];
if (root == null) return "Tree has no nodes.";
return getString(tree, 0, "", true);
}
private static <T extends Comparable<T>> String getString(BinaryHeapArray<T> tree, int index, String prefix, boolean isTail) {
StringBuilder builder = new StringBuilder();
T value = tree.array[index];
builder.append(prefix + (isTail ? "└── " : "├── ") + value + "\n");
List<Integer> children = null;
int leftIndex = getLeftIndex(index);
int rightIndex = getRightIndex(index);
if (leftIndex != Integer.MIN_VALUE || rightIndex != Integer.MIN_VALUE) {
children = new ArrayList<Integer>(2);
if (leftIndex != Integer.MIN_VALUE && leftIndex<tree.size) {
children.add(leftIndex);
}
if (rightIndex != Integer.MIN_VALUE && rightIndex<tree.size) {
children.add(rightIndex);
}
}
if (children != null) {
for (int i = 0; i < children.size() - 1; i++) {
builder.append(getString(tree, children.get(i), prefix + (isTail ? " " : "│ "), false));
}
if (children.size() >= 1) {
builder.append(getString(tree, children.get(children.size() - 1), prefix + (isTail ? " " : "│ "), true));
}
}
return builder.toString();
}
}
}
public static class BinaryHeapTree<T extends Comparable<T>> extends BinaryHeap<T> {
private Type type = Type.MIN;
private int size = 0;
private Node<T> root = null;
/**
* Constructor for heap, defaults to a min-heap.
*/
public BinaryHeapTree() {
root = null;
size = 0;
}
/**
* Constructor for heap.
*
* @param type Heap type.
*/
public BinaryHeapTree(Type type) {
this();
this.type = type;
}
/**
* {@inheritDoc}
*/
@Override
public int size() {
return size;
}
/**
* Get the navigation directions through the tree to the index.
*
* @param index of the Node to get directions for.
* @return Integer array representing the directions to the index.
*/
private int[] getDirections(int index) {
int directionsSize = (int) (Math.log10(index + 1) / Math.log10(2)) - 1;
int[] directions = null;
if (directionsSize > 0) {
directions = new int[directionsSize];
int i = directionsSize - 1;
while (i >= 0) {
index = (index - 1) / 2;
directions[i--] = (index > 0 && index % 2 == 0) ? 1 : 0; // 0=left,
// 1=right
}
}
return directions;
}
/**
* {@inheritDoc}
*/
@Override
public void add(T value) {
add(new Node<T>(null, value));
}
private void add(Node<T> newNode) {
if (root == null) {
root = newNode;
size++;
return;
}
Node<T> node = root;
int[] directions = getDirections(size); // size == index of new node
if (directions != null && directions.length > 0) {
for (int d : directions) {
if (d == 0) {
// Go left
node = node.left;
} else {
// Go right
node = node.right;
}
}
}
if (node.left == null) {
node.left = newNode;
} else {
node.right = newNode;
}
newNode.parent = node;
size++;
heapUp(newNode);
}
/**
* Remove the root node.
*/
private void removeRoot() {
// Find the last node
int[] directions = getDirections(size - 1); // Directions to the last node
Node<T> lastNode = root;
if (directions != null && directions.length > 0) {
for (int d : directions) {
if (d == 0) {
// Go left
lastNode = lastNode.left;
} else {
// Go right
lastNode = lastNode.right;
}
}
}
Node<T> lastNodeParent = null;
if (lastNode.right != null) {
lastNodeParent = lastNode;
lastNode = lastNode.right;
lastNodeParent.right = null;
} else if (lastNode.left != null) {
lastNodeParent = lastNode;
lastNode = lastNode.left;
lastNodeParent.left = null;
}
lastNode.left = root.left;
if (lastNode.left != null) lastNode.left.parent = lastNode;
lastNode.right = root.right;
if (lastNode.right != null) lastNode.right.parent = lastNode;
lastNode.parent = null;
if (!lastNode.equals(root)) root = lastNode;
else root = null;
size--;
heapDown(lastNode);
}
/**
* Get the node in the startingNode sub-tree which has the value.
*
* @param startingNode node rooted sub-tree to search in.
* @param value to search for.
* @return Node<T> which equals value in sub-tree or NULL if not found.
*/
private Node<T> getNode(Node<T> startingNode, T value) {
Node<T> result = null;
if (startingNode != null && startingNode.value.equals(value)) {
result = startingNode;
} else if (startingNode != null && !startingNode.value.equals(value)) {
Node<T> left = startingNode.left;
if (left != null) {
result = getNode(left, value);
if (result != null) return result;
}
Node<T> right = startingNode.right;
if (right != null) {
result = getNode(right, value);
if (result != null) return result;
}
}
return result;
}
/**
* {@inheritDoc}
*/
@Override
public boolean contains(T value) {
if (root==null) return false;
Node<T> node = getNode(root, value);
return (node!=null);
}
/**
* Heap up the heap from this node.
*
* @param node to heap up.
*/
protected void heapUp(Node<T> node) {
while (node != null) {
Node<T> heapNode = (Node<T>) node;
Node<T> parent = heapNode.parent;
if ( (type == Type.MIN && parent != null && node.value.compareTo(parent.value) < 0) ||
(type == Type.MAX && parent != null && node.value.compareTo(parent.value) > 0)
){
// Node is less than parent, switch node with parent
Node<T> grandParent = parent.parent;
Node<T> parentLeft = parent.left;
Node<T> parentRight = parent.right;
parent.left = heapNode.left;
if (parent.left != null) parent.left.parent = parent;
parent.right = heapNode.right;
if (parent.right != null) parent.right.parent = parent;
if (parentLeft != null && parentLeft.equals(node)) {
heapNode.left = parent;
heapNode.right = parentRight;
if (parentRight != null) parentRight.parent = heapNode;
} else {
heapNode.right = parent;
heapNode.left = parentLeft;
if (parentLeft != null) parentLeft.parent = heapNode;
}
parent.parent = heapNode;
if (grandParent == null) {
// New root.
heapNode.parent = null;
root = heapNode;
} else {
Node<T> grandLeft = grandParent.left;
if (grandLeft != null && grandLeft.equals(parent)) {
grandParent.left = heapNode;
} else {
grandParent.right = heapNode;
}
heapNode.parent = grandParent;
}
} else {
node = heapNode.parent;
}
}
}
/**
* Heap down the heap from this node.
*
* @param node to heap down.
*/
protected void heapDown(Node<T> node) {
Node<T> heapNode = (Node<T>) node;
Node<T> left = heapNode.left;
Node<T> right = heapNode.right;
if (left == null && right == null) {
// Nothing to do here
return;
}
Node<T> nodeToMove = null;
if ( (type == Type.MIN && left != null && right != null && node.value.compareTo(left.value) > 0 && node.value.compareTo(right.value) > 0) ||
(type == Type.MAX && left != null && right != null && node.value.compareTo(left.value) < 0 && node.value.compareTo(right.value) < 0)
) {
// Both children are greater/lesser than node
if ((type == Type.MIN && right.value.compareTo(left.value) < 0) ||
(type == Type.MAX && right.value.compareTo(left.value) > 0)
) {
// Right is greater/lesser than left
nodeToMove = right;
} else if ( (type == Type.MIN && left.value.compareTo(right.value) < 0) ||
(type == Type.MAX && left.value.compareTo(right.value) > 0)
){
// Left is greater/lesser than right
nodeToMove = left;
} else {
// Both children are equal, use right
nodeToMove = right;
}
} else if ( (type == Type.MIN && right != null && node.value.compareTo(right.value) > 0) ||
(type == Type.MAX && right != null && node.value.compareTo(right.value) < 0)
) {
// Right is greater than node
nodeToMove = right;
} else if ( (type == Type.MIN && left != null && node.value.compareTo(left.value) > 0) ||
(type == Type.MAX && left != null && node.value.compareTo(left.value) < 0)
) {
// Left is greater than node
nodeToMove = left;
}
// No node to move, stop recursion
if (nodeToMove == null) return;
// Re-factor heap sub-tree
Node<T> nodeParent = heapNode.parent;
if (nodeParent == null) {
// heap down the root
root = nodeToMove;
root.parent = null;
Node<T> nodeToMoveLeft = nodeToMove.left;
Node<T> nodeToMoveRight = nodeToMove.right;
if (heapNode.left.equals(nodeToMove)) {
nodeToMove.left = heapNode;
nodeToMove.right = heapNode.right;
} else {
nodeToMove.left = heapNode.left;
nodeToMove.right = heapNode;
}
heapNode.parent = nodeToMove;
heapNode.left = nodeToMoveLeft;
heapNode.right = nodeToMoveRight;
} else {
// heap down a left
if (nodeParent.left.equals(node)) {
nodeParent.left = nodeToMove;
nodeToMove.parent = nodeParent;
} else {
nodeParent.right = nodeToMove;
nodeToMove.parent = nodeParent;
}
Node<T> nodeLeft = heapNode.left;
Node<T> nodeRight = heapNode.right;
Node<T> nodeToMoveLeft = nodeToMove.left;
Node<T> nodeToMoveRight = nodeToMove.right;
if (heapNode.left.equals(nodeToMove)) {
nodeToMove.right = nodeRight;
if (nodeRight != null) nodeRight.parent = nodeToMove;
nodeToMove.left = heapNode;
heapNode.parent = nodeToMove;
} else {
nodeToMove.left = nodeLeft;
if (nodeLeft != null) nodeLeft.parent = nodeToMove;
nodeToMove.right = heapNode;
heapNode.parent = nodeToMove;
}
heapNode.left = nodeToMoveLeft;
if (nodeToMoveLeft != null) nodeToMoveLeft.parent = heapNode;
heapNode.right = nodeToMoveRight;
if (nodeToMoveRight != null) nodeToMoveRight.parent = heapNode;
}
heapDown(node);
}
/**
* {@inheritDoc}
*/
@Override
public boolean validate() {
if (root==null) return true;
return validateNode(root);
}
/**
* Validate node for heap invariants.
*
* @param node to validate for.
* @return True if node is valid.
*/
private boolean validateNode(Node<T> node) {
Node<T> left = ((Node<T>)node).left;
Node<T> right = ((Node<T>)node).right;
//We shouldn't ever have a right node without a left in a heap
if (right!=null && left==null) return false;
if (left!=null) {
if ((type == Type.MIN && node.value.compareTo(left.value) < 0) || (type == Type.MAX && node.value.compareTo(left.value) > 0)) {
return validateNode(left);
} else {
return false;
}
}
if (right!=null) {
if ((type == Type.MIN && node.value.compareTo(right.value) < 0) || (type == Type.MAX && node.value.compareTo(right.value) > 0)) {
return validateNode(right);
} else {
return false;
}
}
return true;
}
/**
* Populate the node in the array at the index.
*
* @param node to populate.
* @param index of node in array.
* @param array where the node lives.
*/
private void getNodeValue(Node<T> node, int index, T[] array) {
array[index] = node.value;
index = (index * 2) + 1;
Node<T> left = ((Node<T>)node).left;
if (left != null) getNodeValue(left, index, array);
Node<T> right = ((Node<T>)node).right;
if (right != null) getNodeValue(right, index + 1, array);
}
/**
* {@inheritDoc}
*/
@Override
@SuppressWarnings("unchecked")
public T[] getHeap() {
T[] nodes = (T[]) new Comparable[size];
if (root != null) getNodeValue(root, 0, nodes);
return nodes;
}
/**
* {@inheritDoc}
*/
@Override
public T getHeadValue() {
T result = null;
if (root != null) result = root.value;
return result;
}
/**
* {@inheritDoc}
*/
@Override
public T removeHead() {
T result = null;
if (root != null) {
result = root.value;
removeRoot();
}
return result;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return HeapPrinter.getString(this);
}
protected static class HeapPrinter {
public static <T extends Comparable<T>> void print(BinaryHeapTree<T> tree) {
System.out.println(getString(tree.root, "", true));
}
public static <T extends Comparable<T>> String getString(BinaryHeapTree<T> tree) {
if (tree.root == null) return "Tree has no nodes.";
return getString(tree.root, "", true);
}
private static <T extends Comparable<T>> String getString(Node<T> node, String prefix, boolean isTail) {
StringBuilder builder = new StringBuilder();
builder.append(prefix + (isTail ? "└── " : "├── ") + node.value + "\n");
List<Node<T>> children = null;
if (node.left != null || node.right != null) {
children = new ArrayList<Node<T>>(2);
if (node.left != null) children.add(node.left);
if (node.right != null) children.add(node.right);
}
if (children != null) {
for (int i = 0; i < children.size() - 1; i++) {
builder.append(getString(children.get(i), prefix + (isTail ? " " : "│ "), false));
}
if (children.size() >= 1) {
builder.append(getString(children.get(children.size() - 1), prefix + (isTail ? " " : "│ "), true));
}
}
return builder.toString();
}
}
private static class Node<T extends Comparable<T>> {
private T value = null;
private Node<T> parent = null;
private Node<T> left = null;
private Node<T> right = null;
private Node(Node<T> parent, T value) {
this.value = value;
this.parent = parent;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return "value=" + value +
" parent=" + ((parent != null) ? parent.value : "NULL") +
" left=" + ((left != null) ? left.value : "NULL") +
" right=" + ((right != null) ? right.value : "NULL");
}
}
}
}
后续把学习完的数据结构的其他树结构再贴出来。
1
顶
顶
1
踩
踩
分享到：
发表评论
-
对字符串进行验证之前先进行规范化
2013-09-17 23:18 13873对字符串进行验证之前先进行规范化 应用系统中经常对字 ... -
使用telnet连接到基于spring的应用上执行容器中的bean的任意方法
2013-08-08 09:17 1421使用telnet连接到基于spring的应用上执行容器中 ... -
jdk7和8的一些新特性介绍
2013-07-06 16:07 10061更多ppt内容请查看：htt ... -
java对于接口和抽象类的代理实现，不需要有具体实现类
2013-06-12 09:50 2901原文链接：http://www.javaarch.net/j ... -
Java EE 7中对WebSocket 1.0的支持
2013-06-05 09:27 3793原文链接：http://www.javaarch.n ... -
Java Web使用swfobject调用flex图表
2013-05-28 19:05 1072Java Web使用swfobject调用 ... -
spring使用PropertyPlaceholderConfigurer扩展来满足不同环境的参数配置
2013-05-21 15:57 3281spring使用PropertyPlaceholderCon ... -
java国际化
2013-05-20 20:57 4431java国际化 本文来自：http://www.j ... -
RSS feeds with Java
2013-05-20 20:52 1180RSS feeds with Java 原文来自：htt ... -
使用ibatis将数据库从oracle迁移到mysql的几个修改点
2013-04-29 10:40 1625我们项目在公司的大战略下需要从oracle ... -
线上机器jvm dump分析脚本
2013-04-19 10:48 2851#!/bin/sh DUMP_PIDS=`p ... -
eclipse远程部署，静态文件实时同步插件
2013-04-06 20:18 5410eclipse 远程文件实时同步，eclipse远程 ... -
java价格处理的一个问题
2013-03-26 21:21 1782我们经常会处理一些价格，比如从运营上传的文件中将某 ... -
java 服务降级开关设计思路
2013-03-23 16:35 3710java 服务屏蔽开关系统，可以手工降级服务，关闭服 ... -
poi解析excel内存溢出
2013-03-20 22:21 6341真是悲剧啊，一个破内部使用系统20多个人使用的后 ... -
简单web安全框架
2013-03-16 11:56 1494web安全框架,主要用servlet filter方 ... -
基于servlet的简单的页面缓存框架
2013-03-11 19:27 1172基于servlet的页面级缓存框架的基本用法： 代码参考： ... -
Eclipse使用过程中出现java.lang.NoClassDefFoundError的解决方案
2013-02-01 17:22 1466如果jdk，classpath设置正确，突然在eclipse ... -
jetty对于包的加载顺序的处理
2013-01-28 22:58 40601.问题 今天在本地和测试环境用jet ... -
hsqldb源码分析系列6之事务处理
2013-01-20 15:20 1669在session的 public Result ...
相关推荐
Java实现的二叉搜索树和平衡二叉树的代码示例
数据结构 二叉排序树 二叉搜索树 java swing图形界面实现
本教程将向您展示如何使用Java编写代码来执行二叉搜索树的插入操作。我们将提供一个简单而清晰的示例，以帮助您理解如何构建和操作二叉搜索树，并逐步解释代码的思路和逻辑。二叉搜索树（BST）是一种常见的二叉树...
java使用jtree动态实现二叉树，包含二叉树的插入删除很查找
NULL 博文链接：https://128kj.iteye.com/blog/1765663
算法笔记，将有序数组转为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 将有序数组转换为二叉搜索树的结果肯定是不唯一的，因为存在...
3． 由TXT文本中读入一系列的数据，建立一棵平衡二叉树，并实现查找任何数据的功能，并能打印出结点的访问路径。 （Makefile编译）
界面操作二叉树的查找，并可观察结果。是桌面程序
使用java语言编程实现了平衡二叉树、二叉树、二叉搜索树、红黑树四种树相关的数据结构，还实现了多种排序算法。并且是在J2EE下实现的。
二叉树可视化Java语言实现，包含四个字文件、BinaryNode、Show1_12、Display_Tree、TreeControl。直接可以运行，方便快捷。
二叉搜索树在二叉树的基础上，多了一个条件，就是二叉树在插入值时，若插入值比当前节点小，就插入到左节点，否则插入到右节点；若插入过程中，左节点或右节点已经存在，那么继续按如上规则比较，直到遇到一个新的...
设S=(x1,x2,…,xn)是有序集，且x1…，已知键值和区间的存取概率分布为(a0,b1,a1,b2,…,bn,an)，其中ai表示相应区间的搜索概率，bi表示相应键值的...在所有表示有序集的二叉树中找出一棵具有最小平均路长的二叉搜索树
783. 二叉搜索树节点最小距离 给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。 示例： 输入: root = [4,2,6,1,3,null,null] 输出: 1 解释: 注意，root是树节点对象(TreeNode object)，而不是...
第26章介绍了二叉搜索树。二叉树的搜索、插入和删除时间取决于树的高度。在最坏的情况下，高度是O(n)如果一棵树是完全平衡的，也就是说。，一个完整的二叉树——它的高度是log n。是的。但是这样做将是昂贵的。折衷...
1. 二叉搜索树和平衡二叉树有什么关系，强平衡二叉树（AVL 树）和弱平衡二叉树 （红黑树）有什么区别 二叉搜索树：也称二叉查找树，或二叉排序树。定义也比较简单，要么是一颗空 树，要么就是具有如下性质的二叉树：...
二叉树（BinaryTree）、二叉搜索树（BinarySearchTree、BST） 平衡二叉搜索树（BalancedBinarySearchTree、BBST） AVL树（AVLTree）、红黑树（RebBlackTree） B树（B-Tree） 集合（TreeSet）、映射（TreeMap） ...
Java语言，通过栈的方法建立二叉树，递归求最近共同祖先结点
个平衡二叉搜索树的左倾红黑 (LLRB) 实现。 这是 Robert Sedgewick 在 [他的论文](() 和由 Robert Sedgewick 和 Kevin Wayne 撰写的书中介绍的 Java 代码的直接移植。经他们许可，被许可为 LGPL v3，并移植到Python...
将排序数组转换为二叉搜索树 将排序列表转换为二叉搜索树 平衡二叉树 二叉树的最小深度 路径和 路径求和 II 将二叉树展平到链表 在每个节点中填充下一个右指针 II 二叉树最大路径和 根到叶数求和 按算法 动态规划