Learn-Algorithm · ujoyli · Mar 11, 2014 · Mar 20, 2014 · Mar 23, 2014 · Apr 2, 2014
diff --git a/.gitignore b/.gitignore
@@ -86,4 +86,14 @@ coverage.xml
 *.pot
 
 # Sphinx documentation
-docs/_build/
+docs/_build/
+
+
+*.dsw
+*.dsp
+*.ncb
+*.opt
+*.pch
+*.pdb
+*.ilk
+*.idb
diff --git a/1-二叉树/2-平衡树AVL/eddyli/README.md b/1-二叉树/2-平衡树AVL/eddyli/README.md
diff --git a/1-二叉树/3-字典树Trie/eddyli/trie_tree.c b/1-二叉树/3-字典树Trie/eddyli/trie_tree.c
diff --git a/1-二叉树/1-二叉树/eddyli/base-tree.c → 1-树/0-二叉树/eddyli/base-tree.c b/1-二叉树/1-二叉树/eddyli/base-tree.c → 1-树/0-二叉树/eddyli/base-tree.c
diff --git a/1-二叉树/1-二叉树/eddyli/base-tree.h → 1-树/0-二叉树/eddyli/base-tree.h b/1-二叉树/1-二叉树/eddyli/base-tree.h → 1-树/0-二叉树/eddyli/base-tree.h
diff --git a/1-二叉树/1-二叉查找树BST/README.md → 1-树/1-二叉查找树BST/README.md b/1-二叉树/1-二叉查找树BST/README.md → 1-树/1-二叉查找树BST/README.md
diff --git a/1-二叉树/1-二叉查找树BST/eddyli/bst_tree.c → 1-树/1-二叉查找树BST/eddyli/bst_tree.c b/1-二叉树/1-二叉查找树BST/eddyli/bst_tree.c → 1-树/1-二叉查找树BST/eddyli/bst_tree.c
diff --git a/1-二叉树/1-二叉查找树BST/若水清云/若水青云.cpp → 1-树/1-二叉查找树BST/若水清云/若水青云.cpp b/1-二叉树/1-二叉查找树BST/若水清云/若水青云.cpp → 1-树/1-二叉查找树BST/若水清云/若水青云.cpp
diff --git a/1-树/2-平衡树AVL/eddyli/README.md b/1-树/2-平衡树AVL/eddyli/README.md
@@ -0,0 +1,40 @@
+##   插入节点遇到的问题 ##
+在AVLtree上插入一个节点后，需要沿着这个节点向上回溯，重新计算节点的高度，如果高度差大于2，则需要旋转，这里都没有问题，问题就在于，旋转后，树的形状会被破坏，例如
+
+     5
+    / \
+    3  6
+        \
+         9
+          \
+          10
+
+旋转结束后，树变成了这样
+
+      5
+     / \
+    3   \   9
+         \ / \
+          6  10
+
+因为旋转的函数接受的是6这个节点，由于他无法直接找到父节点，所以无法修改父节点的指向，这时候就需要在旋转函数外部修改父节点的指向了
+具体的做法就是把5的右孩纸指向9，在网上找到的一些文章也有这些问题
+
+第二个问题是，如果根节点旋转了，那么树的根就会发生变化，例如
+
+    1
+     \
+      3
+       \
+        6
+
+在6节点插入以后，这棵树旋转成
+
+      3
+     / \
+    1   6
+
+这时候，树的根节点已经变为3了，而不是1了，所以在创建AVLtree的时候，需要及时调整树根节点
+
+
+按照上述思想写完了，感觉写的有点复杂，后来发现其实是自己把问题想复杂了，节点的旋转其实不一定要真正旋转，也就是说，父节点指向的指针是不需要改变的，需要临时申请一个节点，把这个节点当成顶点，最后赋值过去就行了=。=
diff --git a/1-二叉树/2-平衡树AVL/eddyli/avl_tree.c → 1-树/2-平衡树AVL/eddyli/avl_tree.c b/1-二叉树/2-平衡树AVL/eddyli/avl_tree.c → 1-树/2-平衡树AVL/eddyli/avl_tree.c
diff --git a/1-二叉树/3-字典树Trie/eddyli/README.md → 1-树/3-字典树Trie/eddyli/README.md b/1-二叉树/3-字典树Trie/eddyli/README.md → 1-树/3-字典树Trie/eddyli/README.md
diff --git a/1-树/3-字典树Trie/eddyli/trie_tree.c b/1-树/3-字典树Trie/eddyli/trie_tree.c
@@ -0,0 +1,112 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+struct Trie
+{
+  int count;  //count ���Ϊ0��������ǻ�ɫ�㣬count>0�����ǻ�ɫ�㣬ͬʱ��ʾ���ִ���;
+  char value; //�ַ�
+  int childcount; //��������
+  struct Trie ** subtries; //����
+};
+
+typedef struct Trie Trie;
+
+int char2index(char p, Trie* node) {
+	int i = 0;
+	/*
+		since we support all char not only a-z
+		so we must find the char
+		this cause the insert and query
+		method's best time complexity
+		is o(logn) worst Time complexity is o(n)
+		TODO:we should use a map to do char2index
+		so the Time complexity should always be o(logn)
+	*/
+	for (; i < node->childcount; i++) {
+		if (node->subtries[i]->value == p)
+			return i;
+	}
+	return -1;
+}
+
+Trie *_insert(char p, Trie* node) {
+	int index;
+	int count;
+	index = char2index(p, node);
+	count = node->childcount;
+	if (index == -1) {
+		node->subtries = (Trie**)realloc(
+			node->subtries,
+			(count+1) * sizeof(Trie*)
+		);
+		node->subtries[count] = (Trie*)calloc(1, sizeof(Trie));
+		node->subtries[count]->value = p;
+		index = node->childcount;
+		node->childcount += 1;
+	}
+	return node->subtries[index];
+}
+
+Trie *Insert(char *p, int count, Trie* node) {
+	int i;
+	Trie * tnode = node;
+	if (p == NULL || node == NULL || count <= 0)
+		return NULL;
+	for(i = 0; i < count; i++) {
+		tnode = _insert(p[i], tnode);
+	}
+	tnode->count += 1;
+	return tnode;
+}
+
+int Query(char *p, int count, Trie* node) {
+	int i;
+	int index = 0;
+	Trie * _node = node;
+	for (i = 0; i < count; i++) {
+		index = char2index(p[i], _node);
+		if (index == -1)
+			return -1;
+		else
+			_node = _node->subtries[index];
+	}
+	return 0;
+}
+
+
+int Delete(char *p, int count, Trie* node) {
+	int i;
+	int index = 0;
+	Trie * _node = node;
+	for (i = 0; i < count; i++) {
+		index = char2index(p[i], _node);
+		if (index == -1)
+			return -1;
+		else
+			_node = _node->subtries[index];
+	}
+	if (_node->count == 0)
+		return -1;
+	_node->count -= 1;
+	return 0;
+}
+
+
+int main() {
+	Trie node;
+	node.value = ' ';
+	node.childcount = 0;
+	node.count = 0;
+	node.subtries = NULL;
+
+	Insert("hello", 5, &node);
+	Insert("hi", 2, &node);
+	Insert("how", 2, &node);
+	Insert("howmany", 7, &node);
+	Query("hi",2,&node);
+	Query("how",3,&node);
+	Insert("���", 6, &node);
+	Query("���",6,&node);
+	Delete("���",6,&node);
+	printf("%d",Query("���",6,&node));
+}
diff --git a/1-树/4-伸展树Splay/eddyli/README.md b/1-树/4-伸展树Splay/eddyli/README.md
@@ -0,0 +1,27 @@
+## 伸展树 ##
+参考了[这里](http://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A0%91 "这里")的实现
+
+
+其中最关键的操作就是splay函数
+
+这个函数接受一个节点，并且把这个节点通过一系列的旋转转到根部
+,在insert和find后调用splay，将对应的节点调整至根部即可
+
+
+在splay函数中有一个关于双旋转的片段需要仔细考虑：
+
+    else if( x->parent->left == x && x->parent->parent->left == x->parent ) {
+		//这里首先要对x->parent->parent旋转
+    	zig( x->parent->parent );
+    	zig( x->parent );
+    } else if( x->parent->right == x && x->parent->parent->right == x->parent ) {
+    	zag( x->parent->parent );
+    	zag( x->parent );
+    } else if( x->parent->left == x && x->parent->parent->right == x->parent ) {
+		//这里则首先要对x->parent旋转
+    	zig( x->parent );
+    	zag( x->parent );
+    } else {
+    	zag( x->parent );
+    	zig( x->parent );
+    }