在线做头像的网站有哪些,西安酒店网站制作,qq浏览器网页视频怎么下载,seo 的原理和作用介绍
二叉搜索树#xff08;也称二叉排序树#xff09;是符合下面特征的二叉树#xff1a;
树节点增加 key 属性#xff0c;用来比较谁大谁小#xff0c;key 不可以重复对于任意一个树节点#xff0c;它的 key 比左子树的 key 都大#xff0c;同时也比右子树的 key 都… 介绍
二叉搜索树也称二叉排序树是符合下面特征的二叉树
树节点增加 key 属性用来比较谁大谁小key 不可以重复对于任意一个树节点它的 key 比左子树的 key 都大同时也比右子树的 key 都小
查找、插入、删除的时间复杂度与树高相关
如果这棵树左右平衡那么时间复杂度均是 O(logN)这棵树如果左右高度相差过大那么这时是最糟的情况相当于线性查找。时间复杂度是 O(N)。
实现二叉搜索树
public class BSTreeK extends ComparableK, V {public BSNodeK, V root;static class BSNodeK, V {K key;V value;BSNodeK, V left;BSNodeK, V right;public BSNode(K key) {this.key key;}public BSNode(K key, V value) {this.key key;this.value value;}public BSNode(K key, V value, BSNodeK, V left, BSNodeK, V right) {this.key key;this.value value;this.left left;this.right right;}}
}
实现通过key获取值
public V get(K key) {BSNodeK, V node root;while (node ! null) {//当传过来的key为null时会报错int result key.compareTo(node.key);if (result 0) {//说明keynode.keynode node.left;} else if (result 0) {node node.right;} else {return node.value;}}return null;
}
实现获取最小key的值
任何节点的左孩子一定比该节点小因此当遍历到没有左孩子时说明是key最小的节点
public V min() {if (root null) {return null;}BSNodeK, V node root;while (node.left ! null) {node node.left;}return node.value;
}
实现获取最大key的值
任何节点的右孩子一定比该节点大因此当遍历到没有右孩子时说明是key最大的节点
public V max() {if (root null) {return null;}BSNodeK, V node root;while (node.right ! null) {node node.right;}return node.value;
}
实现新增节点
如果key在二叉搜索树中不存在时进行新增如果存在则进行值覆盖
public void put(K key, V value) {BSNodeK, V node root;BSNodeK, V parent null;int result 0;while (node ! null) {parent node;result key.compareTo(node.key);if (result 0) {//说明keynode.keynode node.left;} else if (result 0) {node node.right;} else {//如果存在该节点就覆盖node.value value;return;}}//说明此时没有节点if (parent null){root new BSNodeK,V(key,value);}else if (result0){parent.left new BSNodeK, V(key, value);}else {parent.right new BSNodeK, V(key, value);}
}
实现获取前驱节点
最简单的实现方式是进行一次中序遍历这样可以直接到获取一个升序的排序结果。但是效率较差因此我们采用别的实现方案。 找前驱节点可以根据两个规律去实现 节点有左子树此时前驱节点就是左子树的最大值节点没有左子树若离它最近的祖先自从左而来此祖先即为前驱
public V predecessor(K key) {//祖先节点BSNodeK, V ancestorFromLeft null;BSNodeK, V node root;while (node ! null) {int result key.compareTo(node.key);if (result 0) {node node.left;} else if (result 0) {//如果进入该分支说明该节点可以作为一个祖先节点ancestorFromLeft node;node node.right;} else {break;}}if (nodenull){//说明没有该节点return null;}//如果存在左孩子if (node.left!null){return max(node.left);}//如果不存在左孩子return ancestorFromLeft!null?ancestorFromLeft.value:null;
}
实现获取后驱节点
与获取前驱节点类似也可以通过中序遍历拿到排序结果后寻找指定节点的后驱节点。也可以通过以下两个规律来实现
节点有右子树此时后继节点即为右子树的最小值节点没有右子树若离它最近的祖先自从右而来此祖先即为后继
public V successor(K key){//祖先节点BSNodeK, V ancestorFromLeft null;BSNodeK, V node root;while (node ! null) {int result key.compareTo(node.key);if (result 0) {//如果进入该分支说明该节点可以作为一个祖先节点ancestorFromLeft node;node node.left;} else if (result 0) {node node.right;} else {break;}}if (nodenull){//说明没有该节点return null;}//如果存在左孩子if (node.right!null){return min(node.right);}//如果不存在左孩子return ancestorFromLeft!null?ancestorFromLeft.value:null;
}
实现删除指定节点
删除节点比较麻烦。需要考虑4种情况
被删除节点只存在左孩子被删除节点只存在右孩子被删除节点是根节点被删除节点存在两个孩子节点
前两种情况可以通过被删除节点的父结点来继承被删除节点的子节点来实现。而后两种情况则需要找到被删除节点的后驱节点来顶替被删除节点的位置 public V delete(K key) {//找到被删除节点BSNodeK, V deleteNode root;//找到被删除节点的父结点BSNodeK, V parent null;while (deleteNode ! null) {int result key.compareTo(deleteNode.key);if (result 0) {//说明keynode.keyparent deleteNode;deleteNode deleteNode.left;} else if (result 0) {parent deleteNode;deleteNode deleteNode.right;} else {break;}}if (deleteNode null) {//没找到该节点return null;}//当要删除的节点只存在左节点时if (deleteNode.right null) {shift(parent, deleteNode, deleteNode.left);} else if (deleteNode.left null) { //当要删除的节点只存在右节点时shift(parent, deleteNode, deleteNode.right);} else { //当要删除的节点存在两个子节点时需要找到要删除节点的后驱节点//后驱节点BSNodeK, V s deleteNode.right;//后驱节点的父亲节点。用来判断被删除的节点与其后驱节点是否相邻BSNodeK, V sParent null;while (s.left ! null) {sParent s;s s.left;}//如果要删除的节点与后驱节点不相邻if (sParent ! deleteNode) {//将后驱节点的子节点交给后驱节点的父结点shift(sParent, s, s.right);//后驱节点接管被删除节点的右孩子s.right deleteNode.right;}//如果要删除的节点与后驱节点相邻shift(parent,deleteNode,s);//后驱节点顶替被删除节点的位置s.left deleteNode.left;}return deleteNode.value;}/*** 将要删除的节点的子节点转移到其父结点上** param parent 父结点* param deleteNode 要删除的节点* param child 子节点*/private void shift(BSNodeK, V parent, BSNodeK, V deleteNode, BSNodeK, V child) {if (parent null) {//说明要删除的节点为根节点root child;} else if (deleteNode.left child) {//如果要删除的节点只存在左节点parent.left child;}else {parent.right child;}}
实现范围查询
采用中序遍历得到排序结果后将符合范围的节点返回一个集合
//查找小于key的所有节点的value
public ListV less(K key) {ListV result new ArrayList();LinkedListBSNodeK, V linked new LinkedList();BSNodeK, V node root;while (node ! null || !linked.isEmpty()) {if (node ! null) {linked.push(node);node node.left;} else {BSNodeK, V pop linked.pop();int compare key.compareTo(pop.key);//如果比指定值小if (compare 0) {//加入列表result.add(pop.value);} else {//如果比指定值大没有接着循环的必要break;}node pop.right;}}return result;
}
可以自己实现一下key或是k1valuesk2的代码。
