一、前言 重新梳理整理归纳二叉搜索树。主要参考《C++数据结构与算法》。   二、定义 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。是数据结构中的一类。在一般情况下,查询效率比链表结构要高。 二叉排序树定义,一棵空树,或者是具有下列性质的二叉树: 若左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若右子树不空,则右子树上所有结点的值均大于它的根结点的值; 左、右子树也分别为二叉排序树; 没有键值相等的结点。  …

2020年6月29日 0条评论 10点热度 阅读全文

二叉树: 对于各节点值不重复建树(同时得到后序):(前序+中序建树) TreeNode* build( vector<int>pre , vector<int>in ) { if( !pre.size() || !in.size() ) { return NULL ; } TreeNode* rt = new TreeNode(pre[0]); for( int i = 0 ; i < in.size() ; i++ ) { if( in[i] == pre[0] ) { vector…

2020年2月26日 0条评论 2点热度 阅读全文

1、调整平衡的实现机制不同: 红黑树根据节点颜色(同一双亲节点出发到哨兵节点,所有路径上的黑色节点数目一样),一些约定和旋转实现; AVL根据树的平衡因子(所有节点的左右子树高度差的绝对值不超过1)和旋转决定 2、红黑树的插入效率更高!!! 红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低,任何不平衡都会在三次旋转之内解决,红黑树并不追求“完全平衡”,它只要求部分地达到平衡要求,降低了对旋转的要求,从而提高了性能 而AVL是严格平衡树(高度平衡的二叉搜索树),因此在增加或者删除节点的时候,根据不同情况,旋转的…

2018年8月9日 0条评论 15点热度 阅读全文