bcyy
- 浏览: 1832704 次
-
文章分类
最新评论
-
coosummer：
推荐使用http://buttoncssgenerator.c ...
CSS控制<a>标签变为button -
Allen_J_Will：
哥们，事情没有你说的那么简单，很大的一个项目中，依赖jar包的 ...
struts中java.lang.NoClassDefFoundError: com/opensymphony/xwork2/util/TextUtils的解决办法
二叉搜索树（Binary Search Tree ）的定义及分析
定义：
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：
-
每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同。
-
左子树（如果非空）上所有结点的关键码都小于根结点的关键码。
-
右子树（如果非空）上所有结点的关键码都大于根结点的关键码。
-
左子树和右子树也是二叉搜索树。
-
结点左子树上所有关键码小于结点关键码；
-
右子树上所有关键码大于结点关键码；
-
若从根结点到某个叶结点有一条路径，路径左边的结点的关键码不一定小于路径上的结点的关键码。
-
如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树。 下图为二叉搜索树的一个图
二叉搜索树时一个用于查找操作的搞笑数据结构，因为在最坏的情况下只要查找其中一个分支上的数据就可以了。复杂度为O（nlg n），n为二叉树元素的个数。所以在实际使用中，尽可能的保证二叉树的平衡，这样对搜索来说是最高效的。
二叉树的实现和分析
前面提到，只有当二叉树搜索树保持平衡时对搜索来说才是最高效的，如何保持平衡，实际上很难得。在实际运用中使用最多的就是AVL树，专门在百度百科上专门搜索了下。下面是概述：
********************************************************************************
概述
在计算机科学中，AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。
AVL 节点数计算
高度为 h 的 AVL 树，节点数 N 最多2^h − 1； 最少 （其中）。
最少节点数 n 如以费伯纳西数列可以用数学归纳法证明：
Nh= F【h+ 2】 - 1 (F【h+ 2】是 Fibonacci polynomial 的第h+2个数）。
即：
N0 = 0 （表示 AVL Tree 高度为0的节点总数）
N1 = 1 （表示 AVL Tree 高度为1的节点总数）
N2 = 2 （表示 AVL Tree 高度为2的节点总数）
Nh= N【h− 1】 + N【h− 2】 + 1 （表示 AVL Tree 高度为h的节点总数）
换句话说，当节点数为 N 时，高度 h 最多为。
节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
操作
AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运做的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL 旋转"。
-
单向右旋平衡处理LL：(在百度百科上，这好像写错了）
单向右旋平衡处理LL：(在百度百科上，这好像写错了）
由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；
-
单向左旋平衡处理RR：
由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；
-
双向旋转（先左后右）平衡处理LR：
由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
-
双向旋转（先右后左）平衡处理RL：
由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。
**********************************************************************************
头文件定义：
/*bistree.h*/
#ifndef BISTREE_H
#define BISTREE_H
/*定义平衡因子为AVL树*/
#define AVL_LFT_HEAVY 1
#define AVL_BALANCED 0
#define AVL_RGT_HEAVY -1
/*定义AVL树的节点*/
typedef struct AvlNode_ {
void *data;
int hidden;
int factor;/*平衡因子*/
}AvlNode;
/*定义二叉树结构体*/
typedef struct BisTree_ {
int size;/*存放数据个数*/
int (*compare) (const void *key1,const void *key2);/*预留的一个接口*/
void (*destroy)(void *data);/*封装的析构函数，作用是释放data空间*/
BiTreeNode *root;/*指向根节点的一个指针*/
}BisTree;
/*函数接口*/
void bistree_init (BisTree *tree, int (*compare)(const void *key1,const void
*key2),void (*destroy)(void *data));
void bistree_destory(BisTree *tree);
int bistree_insert(BisTree *tree,const void *data);
int bistree_remove (BisTree *tree,const void *data);
int bistree_lookup(BisTree *tree,void **data);
#define bistree_size(tree) ((tree)->size)
#endif
左旋：（在算法精解上面说的是右旋，和百度百科上描述的一样，但我就按照我理解的写吧）这个单凭看代码真的比较乱的，最好在图纸上画个图，把实现过程画一遍，其他也不是很难理解的。RR可以参照LL右旋的操作。RL也一样。
/*bistree.c*/
#include <stdlib.h>
#include <string.h>
#include "../include/bistree.h"
#include "../include/bitree.h"
/*左旋*/
static void rotate_left(BiTreeNode **node)
{
BiTreeNode *right ,grandchild;
right = bitree_right(*node);
if (((AvlNode *)bitree_data(right) ->factor == AVL_RGT_HEAVY){
/* RR */
bitree_right(*node) = bitree_left(right);
bitree_left(right) = *node;
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right)) ->factor = AVL_BALANCED;
*node = right;
} else { /*RL*/
grandchild = bitree_left(right);
bitree_left(right) = bitree_right(grandchild);
bitree_right(grandchild) = right;
bitree_right(*node) = bitree_left(grandchild);
bitree_left(grandchild) = *node;
switch (((AvlNode *)bitree_data(grandchild)) ->factor){
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(*node)) ->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right)) ->factor = AVL_RGT_HEAVY;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node)) ->factor = AVL_BALANCED;
((AvlNode *)bitree_data(right)) ->factor = AVL_BALANCED;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node)) ->factor = AVL_LFT_HEAVY;
((AvlNode *)bitree_data(right)) ->factor = AVL_BALANCED;
break;
default:
break;
}
((AvlNode *)bitree_data(grandchild)) ->factor = AVL_BALANCED;
*node = grandchild;
}
return;
}
右旋
左旋的逆操作
/*右旋*/
static void rotata_right(BiTreeNode **node)
{
BiTreeNode *left ,grandchild;
left = bitree_left(*node);
if (((AvlNode *)bitree_data(left) ->factor == AVL_LFT_HEAVY){
/* LL */
bitree_left(*node) = bitree_right(left);
bitree_right(left) = *node;
((AvlNode *)bitree_data(*node))->factor = AVL_BALANCED;
((AvlNode *)bitree_data(left)) ->factor = AVL_BALANCED;
*node = left;
} else { /*LR*/
grandchild = bitree_right(left);
bitree_right(left) = bitree_left(grandchild);
bitree_left(grandchild) = left;
bitree_left(*node) = bitree_right(grandchild);
bitree_right(grandchild) = *node;
switch (((AvlNode *)bitree_data(grandchild)) ->factor){
case AVL_LFT_HEAVY:
((AvlNode *)bitree_data(*node)) ->factor = AVL_RGT_HEAVY;
((AvlNode *)bitree_data(left)) ->factor = AVL_BALANCED;
break;
case AVL_BALANCED:
((AvlNode *)bitree_data(*node)) ->factor = AVL_BALANCED;
((AvlNode *)bitree_data(left)) ->factor = AVL_BALANCED;
break;
case AVL_RGT_HEAVY:
((AvlNode *)bitree_data(*node)) ->factor = AVL_BALANCED;
((AvlNode *)bitree_data(left)) ->factor = AVL_LFT_HEAVY;
break;
default:
break;
}
((AvlNode *)bitree_data(grandchild)) ->factor = AVL_BALANCED;
*node = grandchild;
}
return;
}
AVL树初始化及删除节点
/*删除当前节点的左子树
* 如过参数2为NULL,表示删除所有节点
*/
static void destroy_left (BisTree * tree, BiTreeNode * node)
{
BiTreeNode ** position;
/*当树为空时，直接返回*/
if (bistree_size(tree) == 0){
return;
}
/*当删除节点为NULL时，当前位置指向树根
否则，指向当前节点的左子树*/
if (node == NULL){
position = &tree->root;
} else {
position = &node->left;
}
/*删除节点*/
if (*position != NULL){
destroy_left(tree,*position);
destroy_right(tree, *position);
if (tree ->destroy != NULL){
tree->destroy(((AvlNode *)(*position)->data)->data);
}
free ((*position)->data);
free(*position);
*position = NULL;
tree->size --;
}
return ;
}
/*删除节点的右子树
*如果节点为NULL,删除整个树
*/
static void destroy_right(BisTree * tree, BiTreeNode * node)
{
BiTreeNode ** position;
/*当树为空时，直接返回*/
if (bistree_size(tree) == 0){
return;
}
/*当删除节点为NULL时，当前位置指向树根
否则，指向当前节点的左子树*/
if (node == NULL){
position = &tree->root;
} else {
position = &node->right;
}
/*删除节点*/
if (*position != NULL){
destroy_left(tree,*position);
destroy_right(tree, *position);
if (tree ->destroy != NULL){
tree->destroy(((AvlNode *)(*position)->data)->data);
}
free ((*position)->data);
free(*position);
*position = NULL;
tree->size --;
}
return ;
}
/*初始化AVL*/
void bistree_init(BisTree * tree, int(* compare)(const void * key1, const void * key2), void(* destroy)(void * data))
{
bitree_init(tree, destroy);
tree->compare = compare;
return;
}
/*销毁*/
void bistree_destory(BisTree * tree)
{
/*删除所有节点*/
destroy_left( tree, NULL);
memset(tree,0,sizeof(BisTree));
return;
}
插入和删除
static int insert(BisTree *tree,BiTreeNode **node,const void *data,int *balanced)
{
AvlNode *avl_data;
int cmpval,retval;
/**/
if (bitree_is_eob(*node)){/*插入到根节点*/
/*申请空间，并赋值*/
if ((avl_data = (AvlNode *) malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data ->factor = AVL_BALANCED;
avl_data ->hidden = 0;
avl_data -> data = (void *) data;
return bitree_ins_left(tree, * node, avl_data);
} else {/*插入不为空的情况*/
/*比较插入数值与节点数值大小*/
cmpval = tree->compare(data,((AvlNode*)bitree_data(*node))->data);
if (cmpval < 0){
/*插入数值小于节点数值时，插入左子树*/
if (bitree_is_eob(bitree_left(*node))){
/*当插入节点左子树为空时，直接插入并且树平衡*/
if ((avl_data = (AvlNode *) malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data ->factor = AVL_BALANCED;
avl_data ->hidden = 0;
avl_data -> data = (void *) data;
*balanced = 0;
return bitree_ins_left(tree, * node, avl_data);
} else { /*当不为空时，继续判断*/
if (retval = insert( tree, &bitree_left(*node), data, balanced) != 0)
return retval;
}
/*确保树的平衡*/
if (!(*balanced)){
switch (((AvlNode *)bitree_data(*node)->factor){
case AVL_LFT_HEAVY:
rotata_right(node);
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode*)bitree_data(*node) -> factor = AVL_LFT_HEAVY;
break;
case AVL_RGT_HEAVY:
((AvlNode*)bitree_data(*node) -> factor = AVL_BALANCED;
*balanced = 1;
break;
}
}
}else if (cmpval > 0){
/*插入右子树*/
if (bitree_is_eob(bitree_right(*node))){
if ((avl_data = (AvlNode *) malloc(sizeof(AvlNode))) == NULL)
return -1;
avl_data ->factor = AVL_BALANCED;
avl_data ->hidden = 0;
avl_data -> data = (void *) data;
*balanced = 0;
return bitree_ins_right(tree, * node, avl_data);
} else {/*节点不为空时，继续插入*/
if (retval = insert( tree, &bitree_right(*node), data, balanced) != 0)
return retval;
}
/*确保树的平衡*/
if (!(*balanced)){
switch (((AvlNode *)bitree_data(*node)->factor){
case AVL_RGT_HEAVY:
rotata_right(node);
*balanced = 1;
break;
case AVL_BALANCED:
((AvlNode*)bitree_data(*node) -> factor = AVL_RGT_HEAVY;
break;
case AVL_LFT_HEAVY:
((AvlNode*)bitree_data(*node) -> factor = AVL_BALANCED;
*balanced = 1;
break;
}
}
} else { /*cmpval = 0*/
/*插入数据相同*/
if (!((AvlNode *)bitree_data(*node))->hadden){
return 1;
} else {/*将替换掉原来的数值*/
if (tree ->destroy != NULL){
tree ->destroy(((AvlNode*)bitree_data(*node)) ->data);
}
((AvlNode*)bitree_data(*node) -> data = (void *)data;
((AvlNode*)bitree_data(*node) ->hadden = 0;
*balanced = 1;
}
}
}
return 0;
}
static int hide(BisTree *tree, BiTreeNode *node, const void *data)
{
int cmpval,retval;
if (bitree_is_eob(node)
return -1;
cmpval = tree->compare(data,((AvlNode*)bitree_data(node))->data);
if (cmpval < 0 ){/*去左子树查找*/
retval = hide(tree, bitree_left(node),data);
} else if (cmpval > 0){
retval = hide( tree, bitree_right(node), data);
} else {
/*设置为隐藏*/
((AvlNode *)bitree_data(node))->hidden = 1;
retval = 0
}
return retval;
}
/*插入数据
* 返回值:
* 0: 成功
* 1: 插入数据已经存在树中
* -1: 失败
*/
int bistree_insert(BisTree * tree, const void * data)
{
/*balance 作用是设置一个标志位用来对二叉树的
*左右旋操作及设置factor的数值
* 0:表示不平衡，需要重新设置
* 1:则正好相反。
*/
int balance = 0;
return insert(tree,&bitree_root(tree),data,&balance);
}
/*删除数据
* 原则上并未删除这个节点，只是将节点标志设置
* 为隐藏。
*/
int bistree_remove(BisTree * tree, const void * data)
{
return hide (tree,bitree_root(tree),data);
}
查找数据
/*查找数据*/
int look_up(BisTree *tree, BiTreeNode *node, void **data)
{
int cmpval,retval;
if (bitree_is_eob(node))
return -1;
cmpval = tree->compare(data,((AvlNode*)bitree_data(node))->data);
if (cmpval < 0 ){/*去左子树查找*/
retval = look_up(tree, bitree_left(node),data);
} else if (cmpval > 0){
retval = look_up( tree, bitree_right(node), data);
} else {
if (!((AvlNode *)bitree_data(node))->hidden ){
*data = ((AvlNode *)bitree_data(node))->data;
retval =0;
} else {
return -1;
}
}
return retval;
}
右旋
AVL树初始化及删除节点
插入和删除
查找数据
/*查找数据*/
int look_up(BisTree *tree, BiTreeNode *node, void **data)
{
int cmpval,retval;
if (bitree_is_eob(node))
return -1;
cmpval = tree->compare(data,((AvlNode*)bitree_data(node))->data);
if (cmpval < 0 ){/*去左子树查找*/
retval = look_up(tree, bitree_left(node),data);
} else if (cmpval > 0){
retval = look_up( tree, bitree_right(node), data);
} else {
if (!((AvlNode *)bitree_data(node))->hidden ){
*data = ((AvlNode *)bitree_data(node))->data;
retval =0;
} else {
return -1;
}
}
return retval;
}
分享到：
发表评论
相关推荐
C#，二叉搜索树（Binary Search Tree）的迭代方法与源代码 二叉搜索树（BST，Binary Search Tree）又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个...
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node's key. The right ...
二叉搜索树，包括插入、删除、查找、显示等功能
binary search tree 二叉搜索树的C++实现，有插入、删除、查找、查找最大最小等功能，并附有测试例子，简单易懂
是Binary Search Tree code 二叉检索树的代码，实现了插入，删除，检索，遍历，包括先序遍历，中序遍历，后序遍历
二叉排序树（Binary Sorting Tree）又称二叉搜索树（Binary Search Tree），是一种特殊结构的二叉数，作为一种排序和查找的手段，对应有序表的对半查找，通常亦被称为数表。其定义也是递归的。 二叉排序树的定义：...
c++ 二分搜索树 二分查找树 binary search tree BST
二分搜索树（英语：Binary Search Tree），也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件： 若它的左子树不为空，左子树上所有节点的值都小于它的根节点。 若它的右子树不为空，右子...
针对二叉搜索树的编程接口，包括如下接口： 初始化为空树 判断树是否为空 判断树是否已满 确定树中节点个数 向树中添加一个节点 判断树中是否存在某个节点 从树中删除一个节点 将某个函数作用于树中每个节点 删除树...
关于最优二叉查找树的开山之作，介绍了最优二叉查找树的概念，以及构造最优二叉查找树的动态规划算法，来自D. E. KNUTH，发表于1971年，亦可从这里下载：...
给定一棵二叉树，判定该二叉树是否是二叉搜索树（Binary Search Tree）？ 解法1:暴力搜索 首先说明一下二叉树和二叉搜索树的区别。二叉树指这样的树结构，它的每个结点的孩子数目最多为2个；二叉搜索树是一种二叉树...
Binary Search Tree 利用C++實現 Binary Search Tree
最小成本二分检索树optimal binary optimal binary
在这里，我使用 Python Tkinter 制作了二叉搜索树可视化工具 :light_bulb: 我在这里提供的功能----> :right_arrow: 1.二叉搜索树中的插入 :right_arrow: 2.二叉搜索树中的删除 :right_arrow: 3. 二叉搜索树...
Binary_Search_Tree 用java实现的二叉搜索树
红黑树（Red-Black Tree）是二叉搜索树（Binary Search Tree）的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。而红黑树在每一次插入或删除节点 之后...
二叉排序树（BST）又称二叉查找树、二叉搜索树 二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树： 1.若左子树不空，则左子树上所有结点的值均小于根结点的值； 2.若...
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：1.若它的左子树非空，则左子树上所有结点的值均小于根结点的值；2.若它的右...
二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它具有以下特点： 每个节点最多有两个子节点，分别称为左子节点和右子节点。 对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树...
①平衡二叉树(Balanced Binary Tree)是指树中任一结点的左右子树的高度大致相同。 ②任一结点的左右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn)，就可看作是平衡的。 ...