`
java-mans
  • 浏览: 11342943 次
文章分类
社区版块
存档分类
最新评论

二叉查找树(Binary Search Tree)

 
阅读更多

二叉查找树Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树

  1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  3. 它的左、右子树也分别为二叉排序树。

二叉查找树的表示:
class Node {
    int data;
    Node leftChild = null;
    Node rightChild = null;
}

二叉查找树的常用方法:
1. 查找(lookup)
/*
Given a binary tree, return true if a node with the target data is found in the tree. Recurs down the tree, chooses the left or right branch by comparing the target to each node.
*/
static boolean lookup(Node rootNode, int target) {
    // 1. Base case == empty tree
    // in that case, the target is not found so return false
    if (rootNode == null) return false;
    else if (target == rootNode.data) return true;
    else if (target < rootNode.data) return(lookup(rootNode.leftChild, target));
    else return(lookup(rootNode.rightChild, target));
}
2. 最大(max)
	/*
	return the node with maximum key value. It should be last right child of the tree, or the root if the root does not have any child
	*/
	
	public Node maxNode(Node rootNode) {
		while (rootNode.righttChild != null) {
			rootNode = rootNode.rightChild;
		}
		return rootNode;
	}

3. 最小 (min)
	/*
	return the node with minimum key value. It should be last left child of the tree, or the root if the root does not have any child
	*/
	
	public Node minNode(Node rootNode) {
		while (rootNode.leftChild != null) {
			rootNode = rootNode.leftChild;
		}
		return rootNode;
	}

4. 插入(insert)
public static Node insert(Node root, int data) {
	// 1. If the tree is empty, the new node is the root
	if (root == null) {
		return new Node(data);
	}
	else {
		// 2. Otherwise, recur down the tree
		if (data <= root.data) root.leftChild = insert(root.leftChild, data);
		else root.rightChild = insert(root.rightChild, data);
	}
	
	return root;
}


5. in-order tree walk
public void inorder(Node rootNode) {
		if (rootNode != null) {
			inorder(rootNode.leftChild);
			print(nodeNode.data);
			inorder(rootNode.rightChild);
		}
	}

6. successor and predecessor
一个node的successor可以通过in-order walk看出来,因为in-order walk实际上是把二叉查找树做了一个排序。 predecesor 刚好和successor 相反。

Search consists of two cases.
1) If node x has a non-empty right subtree, then x’s successor is the minimum in the right subtree of x.
2) If node x has an empty right subtree, then as long as we move to the left up the tree (move up through right children), we are visiting smaller keys.x’s successor y is the node that x is the predecessor of (x is the maximum in y’s left subtree).In other words, x’s successor y, is the lowest ancestor of x whose left child is also an ancestor of x.
public Node Successor(Node node) {
		if (node.rightChild != null) {
			return minNode(node.rightChild);
		}
		
		Node parentNode = node.parent;
		while (parentNode != null && node == parentNode.rightChild) {
			node = parentNode;
			parentNode = parentNode.parent;
		}
		return parentNode;

	}

If node has two children, its predecessor is the maximumvalue in its left subtree.If it does not have a left child a node's predecessor isits first left ancestor.
public Node Successor(Node node) {
		if (node.rightChild != null) {
			return minNode(node.rightChild);
		}
		
		Node parentNode = node.parent;
		while (parentNode != null && node == parentNode.leftChild) {
			node = parentNode;
			parentNode = parentNode.parent;
		}
		return parentNode;

	}

7. 删除 (delete)

删除一个node x 需要考虑下面几种情况:
case 1:if x has no children, then remove x;
case 2:if x has one child, thenmake p[x] point to child;
case 3:if x has two children (subtrees) ,then swap x with its successor,perform case 0 or case 1 to delete it.

伪代码:

delete(x)
    if x.left = NIL and x.right = NIL //case 1
        if x.parent.left = x
           x.parent.left = NIL
        else
           x.parent.right = NIL
    else if x.left = NIL //case 2a
            connect x.parent to x.right
    else if x.right = NIL //case 2b
            connect x.parent to x.left
    else //case 3
            y = successor(x)
	        connect y.parent to y.right
            replace x with y

8. 求节点的个数(size)
/*
Compute the number of nodes in a tree.
*/
int size(Node rootNode) {
      if (node == NULL) {
      return(0);
      } else {
             return(size(rootNode.leftChild) + 1 + size(rootNode.rightChild));
      }
}

9. 把一个二叉树转成它的“镜像”(mirror)
private void mirror(Node rootNode) {
    if (rootNode != null) {
         // do the sub-trees
         mirror(rootNode.leftChild);
         mirror(rootNode.rightChild);
         // swap the left/right pointers
         Node temp = rootNode.leftChild;
         rootNode.leftChild = rootNode.rightChild;
         rootNode.rightChild = temp;
   }
}
10. check balanced (isBalanced)
To check a binary tree is balanced or not, we can simply convert this question into comparing the maximum depth and minimum depth of the BT, if the diffrence betweenthe maximum depth and minimum depth is larger than 1, the tree is not balanced, otherwise, it is balanced.
int maxDepth(Node rootNode) {
      if (rootNode == null) {
          return 0;
      }

      return 1 + max(maxDepth(rootNode.leftChild), maxDepth(rootNode.rightChild));
}

int minDepth(Node rootNode) {
      if (rootNode == null) {
          return 0;
      }

      return 1 + min(minDepth(rootNode.leftChild), minDepth(rootNode.rightChild));
}

bool isBalanced(Node rootNode) {
      return maxDepth(rootNode) -  minDepth(rootNode) <= 1;
}

11. First common ancestor
查找两个node的最早的公共祖先,分三种情况:
1. 如果两个node在root的两边,那么最早的公共祖先就是root。
2. 如果两个node在root的左边,那么把root.leftChild作为root,再递归。
3.如果两个node在root的右边,那么把root.rightChild作为root,再递归。
     /*
     * get the first common ancestor of node p and node q
     */
    public static Node commonAncestor(Node rootNode, Node p, Node q) {
    	if (covers(rootNode.leftChild, p) && covers(rootNode.leftChild, q))
    		return commonAncestor(rootNode.leftChild, p, q);
    	if (covers(rootNode.rightChild, p) && covers(rootNode.rightChild, q))
    		return commonAncestor(rootNode.rightChild, p, q);
    	return rootNode;
    	
    }
    
    /*
     * check whether the node n is in the tree
     */
    private static boolean covers(Node rootNode, Node n) {
    	if(rootNode == null) return false;
    	if(rootNode == n) return true;
    	return covers(rootNode.leftChild, n) || covers(rootNode.rightChild, n);
    }

如果这个Binary Tree 是 BST的话,可以利用左子树的值小于根节点的值,右子树的值大于根节点的值进行判断两个节点(p, q)的位置,这样更简单。

public Node LCA(Node root, Node p, Node q) {
  if (root == null || p == null || q == null ) return NULL;	
  if (max(p.data, q.data) < root.data)
    return LCA(root.left, p, q);
  else if (min(p.data, q.data) > root.data)
    return LCA(root.right, p, q);
  else
    return root;
}


这个算法的复杂度是O(h)。

12. ISBST()
Given a plain binary tree, examine the tree to determine if itmeets the requirement to be a binary search tree. To be a binary search tree, for every node, all of the nodes in itsleft tree must be <= the node, and all of the nodes in its right subtree must be > the node.
private boolean isBST(Node node) {
      if (node==null) return(true);
      if (node.left!=null && maxValue(node.left) > node.data)  return(false);
      if (node.right!=null && minValue(node.right) <= node.data)  return(false);
       // check that the subtrees themselves are ok
      return( isBST(node.left) && isBST(node.right) );
}
However, the approach given above is very expensive (O(n*h)), because the maxValue(Node node) function will be called n times, and the complexity of the maxValue(Node node) is h (the height of the tree).

Because of the properity of BST, we can simply pass down the minvalue and maxvalue after narrowing the range of the minvalue and maxvalue, and the complexity of this algorithm is O(n). The code below shows the algorithm.
bool isBSTHelper(Node p, int low, int high) {
  if (p == null) return true;
  if (low < p.data && p.data < high)
    return isBSTHelper(p.leftChild, low, p.data) &&
           isBSTHelper(p.rightChild, p.data, high);
  else
    return false;
}
 
bool isBST(Node root) {
  return isBSTHelper(root, INT_MIN, INT_MAX);
}



参考:http://cslibrary.stanford.edu/110/BinaryTrees.html

分享到:
评论

相关推荐

    C#,二叉搜索树(Binary Search Tree)的迭代方法与源代码

    二叉搜索树(BST,Binary Search Tree)又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的,可以使用一个链表数据结构来表示,其中每一个结点就是一个对象。 一般地,除了key和位置数据之外,每个结点...

    二分搜索树-二叉查找树 .docx

    二分搜索树(英语:Binary Search Tree),也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件: 若它的左子树不为空,左子树上所有节点的值都小于它的根节点。 若它的右子树不为空,右子...

    Optimal Binary Search Tree

    关于最优二叉查找树的开山之作,介绍了最优二叉查找树的概念,以及构造最优二叉查找树的动态规划算法,来自D. E. KNUTH,发表于1971年,亦可从这里下载:...

    binary search tree 二叉搜索树的C++实现,有插入、删除、查找、查找最大最小等功能

    binary search tree 二叉搜索树的C++实现,有插入、删除、查找、查找最大最小等功能,并附有测试例子,简单易懂

    二叉排序树的相关代码(插入,删除,创建,遍历)

    二叉排序树(Binary Sorting Tree)又称二叉搜索树(Binary Search Tree),是一种特殊结构的二叉数,作为一种排序和查找的手段,对应有序表的对半查找,通常亦被称为数表。其定义也是递归的。 二叉排序树的定义:...

    BST.rar_binary search tree_二叉搜索树

    二叉搜索树,包括插入、删除、查找、显示等功能

    avl.rar_AVL树_binary search tree

    avl树的插入删除操作,并包括判断输入的二叉查找树是否为avl树,以及把二叉查找树转换为avl树

    数据结构基础之二叉排序树

    二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它具有以下特点: 每个节点最多有两个子节点,分别称为左子节点和右子节点。 对于树中的每个节点,其左子树中的所有节点的值都小于该节点的值,而右子树...

    二叉树的应用:二叉排序树BST和平衡二叉树AVL的构造 课设作业 完整代码

    二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:1.若它的左子树非空,则左子树上所有结点的值均小于根结点的值;2.若它的右...

    二叉搜索树编程接口

    针对二叉搜索树的编程接口,包括如下接口: 初始化为空树 判断树是否为空 判断树是否已满 确定树中节点个数 向树中添加一个节点 判断树中是否存在某个节点 从树中删除一个节点 将某个函数作用于树中每个节点 删除树...

    从B_树、B+_树、B_树谈到R_树.doc

    动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree),红黑树(Red-Black Tree ),B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构,其查找的时间...

    《算法》使用C/C++语言实现二叉排序树

    二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它具有以下特点: 每个结点最多有两个子结点,称为左子结点和右子结点。 对于树中的每个结点,其左子树中的所有结点的值都小于该结点的值,而右子树中的...

    C语言实现二叉查找树(BST)的基本操作

    我们在上一篇博客中讲解了二叉树,这一次我们来实现二叉树的进阶——二叉查找树(Binary Search Tree),又称二插排序树(Binary Sort Tree)。所以简称为BST。二插查找树的定义如下:  1.若左子树不为空,则左子树...

    BinarySortTreeDemo.java

    二叉排序树,完整代码。叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。

    红黑树(Red-Black Tree)代码

    红黑树(Red-Black Tree)是二叉搜索树(Binary Search Tree)的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次插入后)。而红黑树在每一次插入或删除节点 之后...

    数据结构搜索二叉树.rar

    二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树...

    Python实现二叉搜索树的删除功能

    二叉搜索树(二叉查找树,Binary Search Tree)又称为排序二叉树、有序二叉树。 二叉搜索树的实现可以参考:https://blog.csdn.net/weixin_43790276/article/details/105753543 本文使用 Python 实现二叉搜索树的删除...

    非递归实现打印和插入.c

    二叉查找树(Binary Search Tree)-非递归实现打印和插入.c

    Ruby实现的最优二叉查找树算法

    Optimal Binary Search Tree to find by using EditDistance algorithm refer to &lt;&lt;introduction&gt;&gt; example output: “k2 is the root of the tree.” “k1 is the left child of k2.” “d0 is the left ch

    二叉搜索树的实现(Go描述)

    二叉搜索树的结构如下: // Binary Search Tree type BST struct { // Data interface{} 替换为interface可以支持多种数据类型 Val int Left *BST Right *BST } 实现如下操作: 查找(递归/非递归) 删除 插入 ...

Global site tag (gtag.js) - Google Analytics