AVL树简介及实现

<?phprequire 'bstorder.php';$test = range(1, 10);//$test = array(3,9,1,4,8,5,7,6,2,10);$tree = new bst($test, true);//$tree->deletenode('30');(非平衡树可删除,平衡树的没写删除操作)print_r($tree->gettree());?>bstorder.php<?php/*** php实现二叉排序树* @author zhaojian

本文配套源码 /******************************************************************** created: 2007/08/28 filename: avltree.c author: Lichuang purpose: AVL树的实现代码, 参考资料<<数据结构与算法分析-C语言描述>>, 作者Allen Weiss **************************************************

二叉查找树(BSTree)中进行查找.插入和删除操作的时间复杂度都是O(h),其中h为树的高度.BST的高度直接影响到操作实现的性能,最坏情况下,二叉查找树会退化成一个单链表,比如插入的节点序列本身就有序,这时候性能会下降到O(n).可见在树的规模固定的前提下,BST的高度越低越好. 平衡二叉树 平衡二叉树是计算机科学中的一类改进的二叉查找树. 平衡二叉树具有以下性质: (1)一棵空树是平衡二叉树 (2)如果树不为空,它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.

3 实现算法  3.1 数据结构 template<typename T>struct BSTNode//平衡二叉树的结点类型结构体 {        T data;//结点数据类型        int bf;//结点的平衡因子,比二叉链表结点多此项        BSTNode<T>*lchild,*rchild;//左右孩子指针 };   3.2 算法   3.2．1 递归法 递归实现AVL树的节点删除的思想如下.    在AVL树T上删除值为E的节点步骤如下: (1)   

AVL树的删除很多教材上都没有提供,本人对AVL树有着较为深入的研究.现在晒出大体的算法思想.  3.2．1 递归法 递归实现AVL树的结点删除的思想如下.    在AVL树T上删除值为E的结点步骤如下: (1)       若树T为空,返回0退出否则到(2); (2)       比较T的数据和E,若相等跳到(3),若E小于T->data跳到(4),若E大于T->data则跳到(5) (3)       分析T结点的类型 (3.1)若T是叶子结点则直接删除,树变矮即lower=1: (3.2

既然,我们已经证明,保持 AVL 树的平衡将会使性能得到很大的提升,那我们看看如何在程序中向树插入一个新的键值.因为所有的新键是作为叶节点插入树的,而新叶子的平衡因子为零,所以我们对新插入的节点不作调整.不过一旦有新叶子的插入我们必须更新其父节点的平衡因子.新叶子会如何影响父节点的平衡因子取决于叶节点是左子节点还是右子节点.如果新节点是右子节点,父节点的平衡因子减 1.如果新节点是左子节点,父节点的平衡因子将加 1.这种关系可以递归地应用于新节点的前两个节点,并有可能影响到之前的每一个甚至是根节

二叉搜索树的深度与搜索效率 我们在树, 二叉树, 二叉搜索树中提到,一个有n个节点的二叉树,它的最小深度为log(n),最大深度为n.比如下面两个二叉树: 深度为n的二叉树 深度为log(n)的二叉树 这两个二叉树同时也是二叉搜索树(参考树, 二叉树, 二叉搜索树).注意,log以2为基底.log(n)是指深度的量级.根据我们对深度的定义,精确的最小深度为floor(log(n)+1). 我们将处于同一深度的节点归为一层.如果除最后一层外的其他层都被节点填满时,二叉树有最小深度log(n). 二

问题描述 近日在学习AVL树的旋转,尤其是双旋转处有些模糊不清,在MarkAllenWeiss的数据结构与算法分析--C语言描述这本书里面看到,感觉书中的双旋转例程有错误,如下图:这里面的代码显示先右旋,然后左旋,可是注释里面写着是Left-right双旋转,难道不是先左旋,后右旋吗?好像先左旋,后右旋才是正确的做法.请各位指点一下!谢谢.

AVL树的删除算法的两种实现方法 本文是本人原创,当时作为长安大学高一凡老师带的学生,我的毕业设计就是做一个AVL 算法的演示软件.其中,AVL树的删除算法在度娘和 谷歌了很久都没有找到逻辑通畅或者说是我能够看懂的.后来,闭门造成,费了十几张A4纸才把算法设计出来.实现之后得到了老师的认同.非常的开心.之前我骗了大家,用网络上能搜到的算法来敷衍大家,一直觉得我的努力成果,不能让别人剽窃.但是,这么多年过去了.我觉得,我要和CSDN上其他码农一样,需要具有分享精神.... 本文是当时我想投稿的一个